Introduction
Weighted T-systems (also known as weighted marked graphs, weighted event graphs, or synchronous dataflow graphs) are Petri nets in which every place has exactly one input and one output transition, while arcs may carry arbitrary weights. For ordinary (plain) T-systems, liveness is decidable in polynomial time: such a system is live iff every circuit carries a token, or equivalently, iff some firing sequence fires every transition exactly once [7 ] , [1 Thm. 5.31] . A counterpart of the second criterion is known for weighted T-systems [26 ] , but there the vector of ones is replaced by a T-invariant that may be exponentially large [1 Sect. 5.10] . The Petri Net Primer [1 Sect. 5.10] states:
“At the date of publishing this book, no polynomial algorithm appears to be known to check the liveness of weighted T-systems.”
It includes two weighted T-nets (fig:5.23 there) for readers wishing to try a “finger exercise in weighted T-systems”, even just in weighted cycles, also called ring nets, for which it refers to [28 ] . One of the two nets is taken from [9 ] , and recent advances in [10 ] are mentioned. Liveness of weighted circuits was related to the Diophantine problem of Frobenius by Chrz¸astowski-Wachtel and Raczunas [8 ] . The complexity of liveness has also been described as open in the literature on weighted event graphs and synchronous dataflow graphs. Marchetti and Munier-Kordon Marchetti and Munier-Kordon [21 ] write, about liveness and the maximal throughput of timed weighted event graphs, that “the complexity of these two previous problem[s] is still open and is also a challenging theoretical question”, and a survey talk on synchronous dataflow [23 ] still lists the complexity of schedulability (i.e. liveness) and of the maximal throughput as unknown; see also [22 ] , where a polynomially computable sufficient condition for liveness is given.
On the upper-bound side, Hujsa, Berthomieu, Dal Zilio and Le Botlan showed that a weighted circuit is non-live iff the state equation has a solution leading to a dead marking [18, Thm. 6.6], and even iff it has a solution leading to an integer vector, possibly with negative entries, at which no transition is enabled [18 Thm. 6.8] ; with standard bounds on integer programs this puts liveness of ring nets in coNP for binary-encoded numbers. The same authors established a characterisation of this kind for a class that contains all strongly connected weighted T-systems [19 Cor. 6.7] , and derived a coNP upper bound for the structurally bounded systems of that class [19 Sect. 6.2] . This paper supplies a matching lower bound, already for single circuits.
Main result.
By Lemma 3.3, deadlock-freeness and weak liveness of ring nets coincide with liveness, so they are coNP-complete as well. Hardness in Corollary 4.9 holds because ring nets are weighted T-systems, and membership follows from Proposition 3.5 and a known reduction to circuits [18 Prop. 6.3] . In particular, unless P = NP, liveness of weighted T-systems cannot be decided by a pseudo-polynomial algorithm, i.e. in time polynomial in the size of the system and the largest number occurring in it.
The reduction is from Cover: given residue classes r i r_i r i mod b i b_i b i for i = 0 , 1 , … , m − 1 i = 0, 1, \ldots, m - 1 i = 0 , 1 , … , m − 1 , decide whether every integer lies in one of them. The ring consists of m m m “test” places with output weights b i b_i b i , alternating with m m m “buffer” places with output weight W W W , a prime larger than all b i b_i b i (Figure 2 ). The ring behaves like a counter. In each “round”, every buffer transition fires once; after z z z rounds, a further round is possible iff W z Wz W z lies in one of the residue classes, and the test place belonging to the class r i r_i r i mod b i b_i b i checks whether W z ≡ r i ( m o d b i ) Wz \equiv r_i \pmod{b_i} W z ≡ r i ( mod b i ) . So the ring deadlocks after exactly z ∗ z^* z ∗ rounds, where z ∗ z^* z ∗ is the least z ≥ 0 z \ge0 z ≥ 0 such that W z Wz W z avoids all residue classes, and it runs forever if there is no such z z z .
Figure 2. The ring R ( I , W ) R(I,W) R ( I , W ) for m = 3 m = 3 m = 3 . Numbers inside places give the initial marking, labels at arcs the weights; r ˉ i = ( − r i ) m o d b i \bar{r}_i = (-r_i) \bmod b_i r ˉ i = ( − r i ) mod b i , and W > max i b i W > \max_i b_i W > max i b i is coprime to all b i b_i b i . Tokens flow clockwise.
Chip-firing. As a consequence, the halting problem for chip-firing on simple digraphs is NP-complete, and NP-hard already for strongly connected ones (§ 5 ). This answers a question of Farrell and Levine [14 ] , who proved NP-completeness for strongly connected multigraphs; their hard instances may have large edge multiplicities.
Further results, on reversibility and reachability of ring nets and on tractable special cases, are planned for a later version of this paper.
Organisation. Section 2 recalls Petri nets and ring nets. Section 3 characterises liveness of ring nets by deadlock certificates and proves the coNP upper bound. Section 4 gives the reduction, the main result and its extension to weighted T-systems, Section 5 treats chip-firing, and Section 6 concludes.
How this paper came about. On 7 October 2026, the complexity of liveness for ring nets was posed as an open problem to the AI model Claude Opus 5.5 (Anthropic). The model found the reduction from Cover presented in Section 4, also suggested its application to the question of Farrell and Levine on chip-firing (Section 5), and produced a first version of this paper, including computational cross-checks of its claims. The human authors checked the paper (the statements, the proofs and the use of the literature) and, over several rounds, asked for corrections, more detailed arguments and further material. These revisions were carried out with the model and led to the present version, which the authors have checked. The statements of Sections 3–5 were also cross-checked computationally, on exhaustive families of small instances and on many random instances, with two independent implementations; details are planned for the later version.
Preliminaries
Notation. We write N = { 0 , 1 , 2 , … } \mathbb{N} = \{0,1,2,\ldots\} N = { 0 , 1 , 2 , … } for the set of natural numbers (including 0) and Z \mathbb{Z} Z for the set of integers. For an integer x x x and an integer b ≥ 1 b \ge1 b ≥ 1 , ⌊ x / b ⌋ \lfloor x/b \rfloor ⌊ x / b ⌋ is the largest integer that is at most x / b x/b x / b , and
x mod b : = x − b ⌊ x / b ⌋ ∈ { 0 , 1 , … , b − 1 } x \mathbin{\operatorname{mod}} b := x - b\lfloor x/b \rfloor\in\{0,1,\ldots,b-1\} x mod b := x − b ⌊ x / b ⌋ ∈ { 0 , 1 , … , b − 1 }
is the remainder of x x x modulo b b b ; this also applies to negative x x x (for instance, ( − 3 ) mod 4 = 1 (-3) \mathbin{\operatorname{mod}} 4 = 1 ( − 3 ) mod 4 = 1 ). We write b ∣ x b \mid x b ∣ x if b b b divides x x x , and x ≡ x ′ ( m o d b ) x \equiv x' \pmod{b} x ≡ x ′ ( mod b ) if b ∣ x − x ′ b \mid x-x' b ∣ x − x ′ , i.e. if x mod b = x ′ mod b x \mathbin{\operatorname{mod}} b = x' \mathbin{\operatorname{mod}} b x mod b = x ′ mod b .
Lists are written with their first two members, as in s 0 , s 1 , … , s n − 1 s_0,s_1,\ldots,s_{n-1} s 0 , s 1 , … , s n − 1 or j = 1 , 2 , … , k j=1,2,\ldots,k j = 1 , 2 , … , k . Such a list may be shorter than the notation suggests: for n = 1 n=1 n = 1 , the list s 0 , s 1 , … , s n − 1 s_0,s_1,\ldots,s_{n-1} s 0 , s 1 , … , s n − 1 consists of s 0 s_0 s 0 only.
For a finite set X X X , a vector v ∈ Z X v \in\mathbb{Z}^{X} v ∈ Z X (or v ∈ N X v \in\mathbb{N}^{X} v ∈ N X ) is a function v : X → Z v\colon X \to\mathbb{Z} v : X → Z (or into N \mathbb{N} N ). For n ∈ N n \in\mathbb{N} n ∈ N we also write n n n for the set { 0 , 1 , … , n − 1 } \{0,1,\ldots,n-1\} { 0 , 1 , … , n − 1 } ; thus the elements of Z n \mathbb{Z}^{n} Z n are the tuples v = ( v 0 , v 1 , … , v n − 1 ) v=(v_0,v_1,\ldots,v_{n-1}) v = ( v 0 , v 1 , … , v n − 1 ) of integers. We write 0 \mathbf{0} 0 for the zero vector , whose entries are all 0. Vectors are compared componentwise: u ≤ v u \le v u ≤ v means u ( x ) ≤ v ( x ) u(x) \le v(x) u ( x ) ≤ v ( x ) for all x ∈ X x \in X x ∈ X , and u < v u < v u < v means u ( x ) < v ( x ) u(x) < v(x) u ( x ) < v ( x ) for all x ∈ X x \in X x ∈ X . In particular, v ≥ 0 v \ge0 v ≥ 0 means that all entries of v v v are non-negative. For a matrix C ∈ Z S × T C \in\mathbb{Z}^{S \times T} C ∈ Z S × T , i.e. a function C : S × T → Z C\colon S \times T \to\mathbb{Z} C : S × T → Z , and a vector Y ∈ Z T Y \in\mathbb{Z}^{T} Y ∈ Z T , the vector C ⋅ Y ∈ Z S C \cdot Y \in\mathbb{Z}^{S} C ⋅ Y ∈ Z S is defined by ( C ⋅ Y ) ( s ) = ∑ t ∈ T C ( s , t ) Y ( t ) (C \cdot Y)(s) = \sum_{t \in T} C(s,t)Y(t) ( C ⋅ Y ) ( s ) = ∑ t ∈ T C ( s , t ) Y ( t ) .
Petri nets and markings. A Petri net (or simply a net ) is a triple N = ( S , T , F ) N=(S,T,F) N = ( S , T , F ) consisting of
a finite set S S S of places and a finite set T T T of transitions , with S ∩ T = ∅ S \cap T = \varnothing S ∩ T = ∅ ;
a weight function F : ( S × T ) ∪ ( T × S ) → N F\colon(S \times T) \cup(T \times S) \to\mathbb{N} F : ( S × T ) ∪ ( T × S ) → N : there is an arc from a place s s s to a transition t t t iff F ( s , t ) > 0 F(s,t)>0 F ( s , t ) > 0 , and then F ( s , t ) F(s,t) F ( s , t ) is the weight of this arc; similarly for arcs from transitions to places.
A marking of N N N is a vector M ∈ N S M \in\mathbb{N}^{S} M ∈ N S . We think of M ( s ) M(s) M ( s ) as the number of tokens on the place s s s ; in particular, markings are non-negative by definition. A marked net is a pair ( N , M 0 ) (N,M_0) ( N , M 0 ) of a net N N N and a marking M 0 M_0 M 0 of N N N , its initial marking . Notions such as the incidence matrix and T T T -invariants, introduced below, depend only on N N N ; notions such as liveness depend on the marked net. For a transition t t t , the places s s s with F ( s , t ) > 0 F(s,t)>0 F ( s , t ) > 0 are the input places of t t t , and the places s s s with F ( t , s ) > 0 F(t,s)>0 F ( t , s ) > 0 are its output places ; similarly, the transitions t t t with F ( t , s ) > 0 F(t,s)>0 F ( t , s ) > 0 and those with F ( s , t ) > 0 F(s,t)>0 F ( s , t ) > 0 are the input transitions and the output transitions of a place s s s .
Firing. A transition t t t is enabled at a marking M M M if M ( s ) ≥ F ( s , t ) M(s) \ge F(s,t) M ( s ) ≥ F ( s , t ) for all s ∈ S s \in S s ∈ S , i.e. if every input place s s s of t t t carries at least F ( s , t ) F(s,t) F ( s , t ) tokens. An enabled transition t t t can fire (or occur ). Firing t t t removes F ( s , t ) F(s,t) F ( s , t ) tokens from every place s s s and adds F ( t , s ) F(t,s) F ( t , s ) tokens to every place s s s ; it leads to the marking M ′ M' M ′ with
M ′ ( s ) = M ( s ) − F ( s , t ) + F ( t , s ) ( s ∈ S ) , M'(s) = M(s) - F(s,t) + F(t,s) \qquad(s \in S), M ′ ( s ) = M ( s ) − F ( s , t ) + F ( t , s ) ( s ∈ S ) ,
and we write M → t M ′ M \xrightarrow{t} M' M t M ′ . (The vector M ′ M' M ′ is again a marking, i.e. non-negative, because t t t is enabled at M M M .)
We write T ∗ T^* T ∗ for the set of finite words over T T T , including the empty word ε \varepsilon ε . A (finite) firing sequence from a marking M M M is a word σ = t 1 t 2 ⋯ t k ∈ T ∗ \sigma= t_1t_2\cdots t_k \in T^* σ = t 1 t 2 ⋯ t k ∈ T ∗ for which there are markings M = M ( 0 ) , M ( 1 ) , … , M ( k ) M = M^{(0)}, M^{(1)}, \ldots, M^{(k)} M = M ( 0 ) , M ( 1 ) , … , M ( k ) with M ( j − 1 ) → t j M ( j ) M^{(j-1)} \xrightarrow{t_j} M^{(j)} M ( j − 1 ) t j M ( j ) for j = 1 , 2 , … , k j = 1, 2, \ldots, k j = 1 , 2 , … , k ; we then write M → σ M ( k ) M \xrightarrow{\sigma} M^{(k)} M σ M ( k ) , or simply M → σ M \xrightarrow{\sigma} M σ if the final marking does not matter. The length of σ \sigma σ is ∣ σ ∣ = k |\sigma| = k ∣ σ ∣ = k . The empty word ε \varepsilon ε is a firing sequence of length 0 from every marking, and M → ε M M \xrightarrow{\varepsilon} M M ε M . An infinite firing sequence from M M M is an infinite word t 1 t 2 t 3 ⋯ t_1t_2t_3 \cdots t 1 t 2 t 3 ⋯ such that each of its finite prefixes t 1 t 2 ⋯ t k t_1t_2 \cdots t_k t 1 t 2 ⋯ t k is a firing sequence from M M M . A marking M ′ M' M ′ is reachable from M M M if M → σ M ′ M \xrightarrow{\sigma} M' M σ M ′ for some finite firing sequence σ \sigma σ ; the set of all markings reachable from M M M is denoted by [ M ⟩ [M\rangle [ M ⟩ (it contains M M M itself). The markings in [ M 0 ⟩ [M_0\rangle [ M 0 ⟩ are the reachable markings of the marked net ( N , M 0 ) (N,M_0) ( N , M 0 ) .
A marking is dead (or a deadlock ) if it enables no transition. A firing sequence from a marking M M M is maximal if it is infinite, or if it is finite and leads to a dead marking; in other words, if it cannot be extended by a further transition.
Parikh vectors and the state equation. For a finite word σ \sigma σ over T T T , the Parikh vector P ( σ ) ∈ N T \mathcal{P}(\sigma) \in\mathbb{N}^{T} P ( σ ) ∈ N T counts how often each transition occurs in σ \sigma σ : P ( σ ) ( t ) \mathcal{P}(\sigma)(t) P ( σ ) ( t ) is the number of occurrences of t t t in σ \sigma σ ; thus ∣ σ ∣ = ∑ t ∈ T P ( σ ) ( t ) |\sigma| = \sum_{t \in T} \mathcal{P}(\sigma)(t) ∣ σ ∣ = ∑ t ∈ T P ( σ ) ( t ) . The incidence matrix of N N N is the matrix C ∈ Z S × T C \in\mathbb{Z}^{S \times T} C ∈ Z S × T with
C ( s , t ) = F ( t , s ) − F ( s , t ) ( s ∈ S , t ∈ T ) , C(s,t) = F(t,s) - F(s,t) \qquad(s \in S,\ t \in T), C ( s , t ) = F ( t , s ) − F ( s , t ) ( s ∈ S , t ∈ T ) ,
the net change of the number of tokens on s s s caused by one occurrence of t t t . So M → t M ′ M \xrightarrow{t} M' M t M ′ implies M ′ ( s ) = M ( s ) + C ( s , t ) M'(s) = M(s) + C(s,t) M ′ ( s ) = M ( s ) + C ( s , t ) for all s ∈ S s \in S s ∈ S . Adding up these changes along a firing sequence gives the state equation : if M → σ M ′ M \xrightarrow{\sigma} M' M σ M ′ , then
M ′ = M + C ⋅ P ( σ ) . (1) M' = M + C \cdot\mathcal{P}(\sigma). \tag*{(1)} M ′ = M + C ⋅ P ( σ ) . (1)
Formally, this follows by induction on ∣ σ ∣ |\sigma| ∣ σ ∣ : for σ = ε \sigma= \varepsilon σ = ε both sides equal M M M , and if M → σ M ′ ′ → t M ′ M \xrightarrow{\sigma} M'' \xrightarrow{t} M' M σ M ′′ t M ′ , then M ′ ( s ) = M ′ ′ ( s ) + C ( s , t ) = M ( s ) + ( C ⋅ P ( σ ) ) ( s ) + C ( s , t ) = M ( s ) + ( C ⋅ P ( σ t ) ) ( s ) M'(s) = M''(s) + C(s,t) = M(s) + (C \cdot\mathcal{P}(\sigma))(s) + C(s,t) = M(s) + (C \cdot\mathcal{P}(\sigma t))(s) M ′ ( s ) = M ′′ ( s ) + C ( s , t ) = M ( s ) + ( C ⋅ P ( σ )) ( s ) + C ( s , t ) = M ( s ) + ( C ⋅ P ( σ t )) ( s ) for every s s s . The state equation only records how often each transition occurs, not in which order. Its converse does not hold in general: a vector X ∈ N T X \in\mathbb{N}^{T} X ∈ N T with M ′ = M + C ⋅ X M' = M + C \cdot X M ′ = M + C ⋅ X need not be the Parikh vector of any firing sequence from M M M to M ′ M' M ′ (see Example 2.2).
Definition 2.1 (liveness notions, after [1 Def. 3.10] ). Let ( N , M 0 ) (N, M_0) ( N , M 0 ) be a marked net, N = ( S , T , F ) N = (S,T,F) N = ( S , T , F ) , and let t ∈ T t \in T t ∈ T .
t t t is weakly live if some infinite firing sequence from M 0 M_0 M 0 contains t t t infinitely often;
t t t is (strongly) live if for every reachable marking M ∈ [ M 0 ⟩ M \in[M_0\rangle M ∈ [ M 0 ⟩ there is σ ∈ T ∗ \sigma\in T^* σ ∈ T ∗ with M → σ t M \xrightarrow{\sigma t} M σ t , i.e. if from every reachable marking, t t t can still occur.
The marked net ( N , M 0 ) (N, M_0) ( N , M 0 ) is weakly live or (strongly) live if every transition t ∈ T t \in T t ∈ T has the respective property. It is deadlock-free if no reachable marking is dead.
“Live” always means strongly live. Spelled out, ( N , M 0 ) (N, M_0) ( N , M 0 ) is not live iff there are a reachable marking M M M and a transition t t t such that t t t occurs in no firing sequence from M M M , i.e. once M M M has been reached, t t t can never occur. If ( N , M ) (N,M) ( N , M ) is live, we also say that M M M is a live marking of N N N , or simply that M M M is live when N N N is clear from the context; similarly for the other notions of Definition 2.1. Note that a marking that is not live need not be dead: in Example 2.2 below, the marking ( 3 , 0 ) (3,0) ( 3 , 0 ) is not live, although it enables a transition.
Ring nets. A ring net (or ring ) with n ≥ 1 n \ge1 n ≥ 1 places is a net N = ( S , T , F ) N = (S,T,F) N = ( S , T , F ) with S = { s 0 , s 1 , … , s n − 1 } S = \{s_0,s_1,\ldots,s_{n-1}\} S = { s 0 , s 1 , … , s n − 1 } and T = { t 0 , t 1 , … , t n − 1 } T = \{t_0,t_1,\ldots,t_{n-1}\} T = { t 0 , t 1 , … , t n − 1 } , where these 2 n 2n 2 n elements are distinct, such that
a i : = F ( s i , t i ) ≥ 1 and b i : = F ( t i , s i + 1 ) ≥ 1 ( 0 ≤ i ≤ n − 1 ) , a_i := F(s_i,t_i) \ge1 \qquad\text{and}\qquad b_i := F(t_i,s_{i+1}) \ge1 \qquad(0 \le i \le n-1), a i := F ( s i , t i ) ≥ 1 and b i := F ( t i , s i + 1 ) ≥ 1 ( 0 ≤ i ≤ n − 1 ) ,
and F ( x , y ) = 0 F(x,y) = 0 F ( x , y ) = 0 for all other pairs ( x , y ) (x,y) ( x , y ) . Indices are taken modulo n n n throughout, so that s n = s 0 s_n = s_0 s n = s 0 , t − 1 = t n − 1 t_{-1} = t_{n-1} t − 1 = t n − 1 , and so on. So the transition t i t_i t i has the single input place s i s_i s i and the single output place s i + 1 s_{i+1} s i + 1 , and the places and transitions form the circuit s 0 t 0 s 1 t 1 ⋯ s n − 1 t n − 1 s 0 s_0\ t_0\ s_1\ t_1\ \cdots\ s_{n-1}\ t_{n-1}\ s_0 s 0 t 0 s 1 t 1 ⋯ s n − 1 t n − 1 s 0 ; the numbers a i , b i a_i, b_i a i , b i are the weights of the ring. (For n = 1 n = 1 n = 1 , the ring consists of the place s 0 s_0 s 0 , the transition t 0 t_0 t 0 , an arc from s 0 s_0 s 0 to t 0 t_0 t 0 with weight a 0 a_0 a 0 , and an arc from t 0 t_0 t 0 to s 0 s_0 s 0 with weight b 0 b_0 b 0 .) We identify Z T \mathbb{Z}^T Z T with Z n \mathbb{Z}^n Z n via t i ↦ i t_i \mapsto i t i ↦ i , and likewise Z S \mathbb{Z}^S Z S with Z n \mathbb{Z}^n Z n via s i ↦ i s_i \mapsto i s i ↦ i : for Y ∈ Z T Y \in\mathbb{Z}^T Y ∈ Z T we write Y i = Y ( t i ) Y_i = Y(t_i) Y i = Y ( t i ) , and a marking M M M is written as ( M ( s 0 ) , M ( s 1 ) , … , M ( s n − 1 ) ) (M(s_0), M(s_1), \ldots, M(s_{n-1})) ( M ( s 0 ) , M ( s 1 ) , … , M ( s n − 1 )) .
The transition t i t_i t i is enabled at a marking M M M if M ( s i ) ≥ a i M(s_i) \geq a_i M ( s i ) ≥ a i , and firing t i t_i t i removes a i a_i a i tokens from s i s_i s i and adds b i b_i b i tokens to s i + 1 s_{i+1} s i + 1 . In particular, a marking D D D is dead iff D ( s i ) < a i D(s_i) < a_i D ( s i ) < a i for all i i i . Each place s i s_i s i has exactly one input transition, t i − 1 t_{i-1} t i − 1 , and one output transition, t i t_i t i . Hence the incidence matrix C C C of the ring satisfies, for every Y ∈ Z n Y \in\mathbb{Z}^n Y ∈ Z n ,
( C ⋅ Y ) ( s i ) = b i − 1 Y i − 1 − a i Y i ( 0 ≤ i ≤ n − 1 ) (2) (C \cdot Y)(s_i) = b_{i-1}Y_{i-1} - a_iY_i \qquad(0 \leq i \leq n - 1) \tag*{(2)} ( C ⋅ Y ) ( s i ) = b i − 1 Y i − 1 − a i Y i ( 0 ≤ i ≤ n − 1 ) (2)
place s i s_i s i gains b i − 1 b_{i-1} b i − 1 tokens with each occurrence of t i − 1 t_{i-1} t i − 1 and loses a i a_i a i tokens with each occurrence of t i t_i t i . This also holds for n = 1 n = 1 n = 1 , where t i − 1 = t i = t 0 t_{i-1} = t_i = t_0 t i − 1 = t i = t 0 and ( C ⋅ Y ) ( s 0 ) = ( b 0 − a 0 ) Y 0 (C \cdot Y)(s_0) = (b_0 - a_0)Y_0 ( C ⋅ Y ) ( s 0 ) = ( b 0 − a 0 ) Y 0 .
Example 2.2 (running example). Let N N N be the ring with n = 2 n = 2 n = 2 , a 0 = 2 a_0 = 2 a 0 = 2 , b 0 = 3 b_0 = 3 b 0 = 3 , a 1 = 6 a_1 = 6 a 1 = 6 and $b_1 = 4 (Figure 1 ): t 0 t_0 t 0 takes 2 tokens from s 0 s_0 s 0 and puts 3 tokens on s 1 s_1 s 1 , and t 1 t_1 t 1 takes 6 tokens from s 1 s_1 s 1 and puts 4 tokens on s 0 s_0 s 0 . Markings are pairs ( M ( s 0 ) , M ( s 1 ) ) (M(s_0), M(s_1)) ( M ( s 0 ) , M ( s 1 )) . By (2) ,
( C ⋅ Y ) ( s 0 ) = 4 Y 1 − 2 Y 0 , ( C ⋅ Y ) ( s 1 ) = 3 Y 0 − 6 Y 1 . (C \cdot Y)(s_0) = 4Y_1 - 2Y_0,\qquad(C \cdot Y)(s_1) = 3Y_0 - 6Y_1. ( C ⋅ Y ) ( s 0 ) = 4 Y 1 − 2 Y 0 , ( C ⋅ Y ) ( s 1 ) = 3 Y 0 − 6 Y 1 .
From M 0 = ( 4 , 0 ) M_0 = (4, 0) M 0 = ( 4 , 0 ) only t 0 t_0 t 0 is enabled, and ( 4 , 0 ) → t 0 ( 2 , 3 ) → t 0 ( 0 , 6 ) → t 1 ( 4 , 0 ) (4, 0) \xrightarrow{t_0} (2, 3) \xrightarrow{t_0} (0, 6) \xrightarrow{t_1} (4, 0) ( 4 , 0 ) t 0 ( 2 , 3 ) t 0 ( 0 , 6 ) t 1 ( 4 , 0 ) . At ( 2 , 3 ) (2, 3) ( 2 , 3 ) only t 0 t_0 t 0 is enabled, and at ( 0 , 6 ) (0, 6) ( 0 , 6 ) only t 1 t_1 t 1 . So the reachable markings of ( N , M 0 ) (N, M_0) ( N , M 0 ) are ( 4 , 0 ) (4, 0) ( 4 , 0 ) , ( 2 , 3 ) (2, 3) ( 2 , 3 ) and ( 0 , 6 ) (0, 6) ( 0 , 6 ) , the only maximal firing sequence from M 0 M_0 M 0 is the infinite sequence t 0 t 0 t 1 t 0 t 0 t 1 t 0 t 0 t 1 ⋯ t_0t_0t_1\ t_0t_0t_1\ t_0t_0t_1\ \cdots t 0 t 0 t 1 t 0 t 0 t 1 t 0 t 0 t 1 ⋯ , and M 0 M_0 M 0 is live: from each reachable marking, both transitions can occur again. The Parikh vector of t 0 t 0 t 1 t_0t_0t_1 t 0 t 0 t 1 is ( 2 , 1 ) (2, 1) ( 2 , 1 ) , and indeed ( 4 , 0 ) + C ⋅ ( 2 , 1 ) = ( 4 + 4 − 4 , 0 + 6 − 6 ) = ( 4 , 0 ) (4, 0) + C \cdot(2, 1) = (4 + 4 - 4, 0 + 6 - 6) = (4, 0) ( 4 , 0 ) + C ⋅ ( 2 , 1 ) = ( 4 + 4 − 4 , 0 + 6 − 6 ) = ( 4 , 0 ) , in accordance with the state equation (2.1).
From the marking ( 3 , 0 ) (3, 0) ( 3 , 0 ) we get ( 3 , 0 ) → t 0 ( 1 , 3 ) (3, 0) \xrightarrow{t_0} (1, 3) ( 3 , 0 ) t 0 ( 1 , 3 ) , and ( 1 , 3 ) (1, 3) ( 1 , 3 ) is dead because 1 < 2 1 < 2 1 < 2 and 3 < 6 3 < 6 3 < 6 . So the marking ( 3 , 0 ) (3, 0) ( 3 , 0 ) is not live, although it is not dead. The vector X = ( 2 , 1 ) X = (2, 1) X = ( 2 , 1 ) satisfies ( 3 , 0 ) + C ⋅ X = ( 3 , 0 ) (3, 0) + C \cdot X = (3, 0) ( 3 , 0 ) + C ⋅ X = ( 3 , 0 ) , but no firing sequence from ( 3 , 0 ) (3, 0) ( 3 , 0 ) has the Parikh vector ( 2 , 1 ) (2, 1) ( 2 , 1 ) : the state equation is necessary for reachability, but not sufficient.
Figure 1. The ring of Example 2.2: n = 2 n = 2 n = 2 , ( a 0 , a 1 ) = ( 2 , 6 ) (a_0, a_1) = (2, 6) ( a 0 , a 1 ) = ( 2 , 6 ) , ( b 0 , b 1 ) = ( 3 , 4 ) (b_0, b_1) = (3, 4) ( b 0 , b 1 ) = ( 3 , 4 ) , with the marking M 0 = ( 4 , 0 ) M_0 = (4, 0) M 0 = ( 4 , 0 ) . Numbers inside places give the marking, labels at arcs the weights.
T-invariants. By the state equation, a firing sequence σ \sigma σ from a marking M M M leads back to M M M if C ⋅ P ( σ ) = 0 C \cdot\mathcal{P}(\sigma) = 0 C ⋅ P ( σ ) = 0 . A vector x ∈ N T x \in\mathbb{N}^T x ∈ N T with C ⋅ x = 0 C \cdot x = 0 C ⋅ x = 0 is called a T T T -invariant of N N N ; it describes how often each transition has to occur so that the total effect on the marking is zero. A ring is token-conserving if a i = b i a_i = b_i a i = b i for all i i i , i.e. if every occurrence of every transition preserves the total number of tokens.
Lemma 2.3 (T-invariants of token-conserving rings). Let N N N be a token-conserving ring with n n n places and weights a i = b i a_i = b_i a i = b i , and let L : = lcm ( a 0 , a 1 , … , a n − 1 ) L := \operatorname{lcm}(a_0, a_1, \ldots, a_{n-1}) L := lcm ( a 0 , a 1 , … , a n − 1 ) . Then the vector x T ∈ N T x_T \in\mathbb{N}^T x T ∈ N T with
x T ( t i ) = L / a i x_T(t_i) = L/a_i x T ( t i ) = L / a i for all i i i is a T T T -invariant of N N N , and the T T T -invariants of N N N are exactly the vectors k x T k x_T k x T with k ∈ N k \in\mathbb{N} k ∈ N . We call x T x_T x T the minimal T-invariant of N N N .
Proof. By (2) with b i − 1 = a i − 1 b_{i-1} = a_{i-1} b i − 1 = a i − 1 , a vector x ∈ N n x \in\mathbb{N}^n x ∈ N n satisfies C ⋅ x = 0 C \cdot x = 0 C ⋅ x = 0 iff a i x i = a i − 1 x i − 1 a_i x_i = a_{i-1}x_{i-1} a i x i = a i − 1 x i − 1 for all i i i , i.e. iff the product a i x i a_i x_i a i x i has the same value c c c for all i i i . In this case x i = c / a i x_i = c/a_i x i = c / a i is an integer for every i i i , so c ∈ N c \in\mathbb{N} c ∈ N is a common multiple of a 0 , a 1 , … , a n − 1 a_0, a_1, \ldots, a_{n-1} a 0 , a 1 , … , a n − 1 , i.e. c = k L c = kL c = k L for some k ∈ N k \in\mathbb{N} k ∈ N , and then x = k x T x = kx_T x = k x T . Conversely, k x T kx_T k x T is a T T T -invariant for every k ∈ N k \in\mathbb{N} k ∈ N , since a i ⋅ k L / a i = k L a_i \cdot kL/a_i = kL a i ⋅ k L / a i = k L for all i i i .
Encodings and the problem. A ring net is given by the number n n n of places and the weights a i , b i a_i, b_i a i , b i , and a marking M M M by the numbers M ( s i ) M(s_i) M ( s i ) , for 0 ≤ i ≤ n − 1 0 \leq i \leq n - 1 0 ≤ i ≤ n − 1 . Unless stated otherwise, numbers are written in binary, and the size of an instance is the total number of bits needed to write it down. A decision problem is in NP if its yes-instances have certificates of polynomial size that can be checked in polynomial time, and it is in coNP if its complement is in NP, i.e. if its no-instances have such certificates. A polynomial-time reduction from a problem A A A to a problem B B B is also a reduction from the complement of A A A to the complement of B B B ; hence a problem is coNP-hard iff its complement is NP-hard. A problem is coNP-hard in the strong sense if it remains coNP-hard when restricted to instances whose numbers are bounded by a polynomial in the size of the instance; equivalently, if it is coNP-hard even when all numbers are written in unary; NP-hardness in the strong sense is defined in the same way. We study the problem
RingLive: given a ring net N N N and a marking M 0 M_0 M 0 of N N N , is M 0 M_0 M 0 live, i.e. is the marked ring ( N , M 0 ) (N, M_0) ( N , M 0 ) live?
Deadlock certificates and the upper bound
The results of this section are essentially known, from the work of Hujsa, Berthomieu, Dal Zilio and Le Botlan: for rings, the equivalence (1)⇔ \Leftrightarrow ⇔ (6) in Lemma 3.3 is [18 Thm. 6.6] , the equivalence (1)⇔ \Leftrightarrow ⇔ (5) is [18 Thm. 6.8] , and Corollary 3.4 is close to [18 Thm. 6.7] . The coNP upper bound (Proposition 3.5 ) follows from (1)⇔ \Leftrightarrow ⇔ (6) directly with standard bounds on integer programs, and the same authors stated such a bound for the structurally bounded systems of a larger class [19 Sect. 6.2] . We give short direct proofs for rings, because Sections 4 and 5 use these results in exactly this form.
Throughout this section, N N N is a ring net with the n n n places s 0 , s 1 , … , s n − 1 s_0, s_1, \ldots, s_{n-1} s 0 , s 1 , … , s n − 1 , the transitions t 0 , t 1 , … , t n − 1 t_0, t_1, \ldots, t_{n-1} t 0 , t 1 , … , t n − 1 , the weights a i , b i a_i, b_i a i , b i and the incidence matrix C C C , and M 0 M_0 M 0 is a marking of N N N ; indices are taken modulo n n n . For a finite firing sequence σ \sigma σ we write P ( σ ) i \mathcal{P}(\sigma)_i P ( σ ) i for the number of occurrences of t i t_i t i in σ \sigma σ .
The idea. If M 0 M_0 M 0 is not live, then some firing sequence ρ \rho ρ leads from M 0 M_0 M 0 to a dead marking D D D (this is shown in Lemma 3.3 below). By the state equation, its Parikh vector Y = P ( ρ ) Y = \mathcal{P}(\rho) Y = P ( ρ ) satisfies D = M 0 + C ⋅ Y D = M_0 + C \cdot Y D = M 0 + C ⋅ Y , so Y Y Y witnesses that M 0 M_0 M 0 is not live. The main point of this section (Lemma 3.1) is a converse: any vector Y ∈ N n Y \in\mathbb{N}^n Y ∈ N n for which M 0 + C ⋅ Y M_0 + C \cdot Y M 0 + C ⋅ Y is below all enabling thresholds bounds all behaviours of ( N , M 0 ) (N, M_0) ( N , M 0 ) , even if Y Y Y is not the Parikh vector of any firing sequence. So non-liveness has certificates that are easy to check, and it remains to show that small certificates exist.
Deadlock certificates. A vector Y ∈ N n Y \in\mathbb{N}^n Y ∈ N n is a deadlock certificate for ( N , M 0 ) (N, M_0) ( N , M 0 ) if
( M 0 + C ⋅ Y ) ( s i ) < a i for all i ∈ { 0 , 1 , … , n − 1 } . (3) (M_0 + C \cdot Y)(s_i) < a_i \qquad\text{for all } i \in\{0,1,\ldots,n-1\}. \tag*{(3)} ( M 0 + C ⋅ Y ) ( s i ) < a i for all i ∈ { 0 , 1 , … , n − 1 } . (3)
We do not require M 0 + C ⋅ Y ≥ 0 M_0 + C \cdot Y \geq0 M 0 + C ⋅ Y ≥ 0 . If M 0 + C ⋅ Y ≥ 0 M_0 + C \cdot Y \geq0 M 0 + C ⋅ Y ≥ 0 does hold, then M 0 + C ⋅ Y M_0 + C \cdot Y M 0 + C ⋅ Y is a marking at which no t i t_i t i is enabled, i.e. a dead marking. In particular, by the state equation, the Parikh vector of every firing sequence from M 0 M_0 M 0 to a dead marking is a deadlock certificate. In Example 2.2 with the marking M 0 = ( 3 , 0 ) M_0 = (3,0) M 0 = ( 3 , 0 ) , the vector Y = ( 1 , 0 ) Y = (1,0) Y = ( 1 , 0 ) is a deadlock certificate: ( 3 , 0 ) + C ⋅ Y = ( 1 , 3 ) (3,0) + C \cdot Y = (1,3) ( 3 , 0 ) + C ⋅ Y = ( 1 , 3 ) , and 1 < 2 1 < 2 1 < 2 , 3 < 6 3 < 6 3 < 6 .
Lemma 3.1 (certificates bound all behaviours). Let Y Y Y be a deadlock certificate for ( N , M 0 ) (N,M_0) ( N , M 0 ) . Then P ( σ ) ≤ Y \mathcal{P}(\sigma) \leq Y P ( σ ) ≤ Y for every finite firing sequence σ \sigma σ from M 0 M_0 M 0 . Consequently, every firing sequence from M 0 M_0 M 0 has length at most ∑ i Y i \sum_i Y_i ∑ i Y i , and there is no infinite firing sequence from M 0 M_0 M 0 .
Idea. Consider the first moment at which some transition t i t_i t i would occur for the ( Y i + 1 ) (Y_i+1) ( Y i + 1 ) -st time. Up to this moment, t i − 1 t_{i-1} t i − 1 has occurred at most Y i − 1 Y_{i-1} Y i − 1 times, so s i s_i s i has received at most b i − 1 Y i − 1 b_{i-1}Y_{i-1} b i − 1 Y i − 1 tokens, and after Y i Y_i Y i occurrences of t i t_i t i fewer than a i a_i a i tokens are left on s i s_i s i , by (3) . So t i t_i t i cannot occur once more. The proof makes this precise by induction.
Proof. We show P ( σ ) ≤ Y \mathcal{P}(\sigma) \leq Y P ( σ ) ≤ Y by induction on ∣ σ ∣ \lvert\sigma\rvert ∣ σ ∣ . For σ = ε \sigma= \varepsilon σ = ε , we have P ( ε ) = 0 ≤ Y \mathcal{P}(\varepsilon) = 0 \leq Y P ( ε ) = 0 ≤ Y , since Y ∈ N n Y \in\mathbb{N}^n Y ∈ N n .
For the induction step, let σ t i \sigma t_i σ t i be a firing sequence from M 0 M_0 M 0 , say M 0 → σ M → t i M_0 \xrightarrow{\sigma} M \xrightarrow{t_i} M 0 σ M t i , and assume P ( σ ) ≤ Y \mathcal{P}(\sigma) \leq Y P ( σ ) ≤ Y . The vector P ( σ t i ) \mathcal{P}(\sigma t_i) P ( σ t i ) differs from P ( σ ) \mathcal{P}(\sigma) P ( σ ) only in its i i i -th entry, which is larger by 1. If P ( σ ) i < Y i \mathcal{P}(\sigma)_i < Y_i P ( σ ) i < Y i , then P ( σ t i ) i ≤ Y i \mathcal{P}(\sigma t_i)_i \leq Y_i P ( σ t i ) i ≤ Y i , and we are done. By the induction hypothesis, the only other case is P ( σ ) i = Y i \mathcal{P}(\sigma)_i = Y_i P ( σ ) i = Y i ; we show that it cannot occur. By the state equation (1) and by (2) , the number of tokens on s i s_i s i at M M M is
M ( s i ) = M 0 ( s i ) + b i − 1 P ( σ ) i − 1 − a i P ( σ ) i ≤ M 0 ( s i ) + b i − 1 Y i − 1 − a i Y i = ( M 0 + C ⋅ Y ) ( s i ) < a i , M(s_i) = M_0(s_i) + b_{i-1}\mathcal{P}(\sigma)_{i-1} - a_i\mathcal{P}(\sigma)_i \leq M_0(s_i) + b_{i-1}Y_{i-1} - a_iY_i = (M_0 + C \cdot Y)(s_i) < a_i, M ( s i ) = M 0 ( s i ) + b i − 1 P ( σ ) i − 1 − a i P ( σ ) i ≤ M 0 ( s i ) + b i − 1 Y i − 1 − a i Y i = ( M 0 + C ⋅ Y ) ( s i ) < a i ,
where we used P ( σ ) i − 1 ≤ Y i − 1 \mathcal{P}(\sigma)_{i-1} \leq Y_{i-1} P ( σ ) i − 1 ≤ Y i − 1 (induction hypothesis), b i − 1 > 0 b_{i-1} > 0 b i − 1 > 0 , P ( σ ) i = Y i \mathcal{P}(\sigma)_i = Y_i P ( σ ) i = Y i and (3) . But t i t_i t i is enabled at M M M , i.e. M ( s i ) ≥ a i M(s_i) \geq a_i M ( s i ) ≥ a i , a contradiction. (For n = 1 n = 1 n = 1 , the indices i − 1 i-1 i − 1 and i i i coincide, P ( σ ) i − 1 = P ( σ ) i = Y i \mathcal{P}(\sigma)_{i-1} = \mathcal{P}(\sigma)_i = Y_i P ( σ ) i − 1 = P ( σ ) i = Y i , and the same computation applies.)
Finally, ∣ σ ∣ = ∑ i P ( σ ) i ≤ ∑ i Y i \lvert\sigma\rvert= \sum_i \mathcal{P}(\sigma)_i \leq\sum_i Y_i ∣ σ ∣ = ∑ i P ( σ ) i ≤ ∑ i Y i for every finite firing sequence σ \sigma σ from M 0 M_0 M 0 . An infinite firing sequence from M 0 M_0 M 0 would have finite prefixes of every length, which is impossible. □ \square □
Lemma 3.2 (a transition that stops firing stops the whole ring). Let M M M be a marking of N N N .
(a) In every infinite firing sequence from M M M , every transition occurs infinitely often.
(b) If some transition occurs in no firing sequence from M M M , then a dead marking is reachable from M M M .
Idea. Tokens arrive at s i s_i s i only through t i − 1 t_{i-1} t i − 1 . So if one transition stops firing for good, then so does the next one, then the one after it, and so on around the ring, until no transition can fire any more.
Proof. (a) Let τ 1 τ 2 τ 3 ⋯ \tau_1\tau_2\tau_3\cdots τ 1 τ 2 τ 3 ⋯ be an infinite firing sequence from M M M . Since there are only n n n transitions, some transition occurs in it infinitely often. Suppose, for a contradiction, that some transition occurs in it only finitely often. Starting at a transition that occurs infinitely often and going backwards around the ring, i.e. through t j , t j − 1 , t j − 2 , … t_j,t_{j-1},t_{j-2},\ldots t j , t j − 1 , t j − 2 , … , we eventually meet a transition that occurs only finitely often. Hence there is an index i i i such that t i t_i t i occurs infinitely often, but t i − 1 t_{i-1} t i − 1 only finitely often. (This is impossible for n = 1 n = 1 n = 1 , where t i − 1 = t i t_{i-1} = t_i t i − 1 = t i ; so for n = 1 n = 1 n = 1 there is nothing more to show.) Choose k k k so that t i − 1 t_{i-1} t i − 1 does not occur among t k + 1 , t k + 2 , … t_{k+1},t_{k+2},\ldots t k + 1 , t k + 2 , … , and let M → τ 1 τ 2 ⋯ τ k M ′ M \xrightarrow{\tau_1\tau_2\cdots\tau_k} M' M τ 1 τ 2 ⋯ τ k M ′ . After position k k k , no tokens are added to s i s_i s i , because t i − 1 t_{i-1} t i − 1 is the only input transition of s i s_i s i , and each occurrence of t i t_i t i removes a i ≥ 1 a_i \geq1 a i ≥ 1 tokens from s i s_i s i . Since the number of tokens on s i s_i s i never becomes negative, t i t_i t i occurs at most M ′ ( s i ) / a i M'(s_i)/a_i M ′ ( s i ) / a i times after position k k k . This contradicts the choice of i i i .
(b) Let t t t be a transition that occurs in no firing sequence from M M M , and suppose, for a contradiction, that no dead marking is reachable from M M M . Then every marking reachable from M M M enables some transition. Starting at M M M and firing, at each step, some transition that is enabled at the current marking (which is again reachable from M M M ), we obtain an infinite firing sequence from M M M . By (a), t t t occurs in it, say at position k k k . Then the prefix of length k k k is a firing sequence from M M M in which t t t occurs, a contradiction.
Lemma 3.3 (characterisation). For a ring net N N N and a marking M 0 M_0 M 0 of N N N the following are equivalent:
( N , M 0 ) (N,M_0) ( N , M 0 ) is live;
( N , M 0 ) (N,M_0) ( N , M 0 ) is deadlock-free;
( N , M 0 ) (N,M_0) ( N , M 0 ) is weakly live;
there is an infinite firing sequence from M 0 M_0 M 0 ;
( N , M 0 ) (N,M_0) ( N , M 0 ) has no deadlock certificate, i.e. there is no Y ∈ N n Y \in\mathbb{N}^{n} Y ∈ N n with ( M 0 + C ⋅ Y ) ( s i ) < a i (M_0+C\cdot Y)(s_i)<a_i ( M 0 + C ⋅ Y ) ( s i ) < a i for all i i i ;
there is no Y ∈ N n Y \in\mathbb{N}^{n} Y ∈ N n such that M 0 + C ⋅ Y M_0+C\cdot Y M 0 + C ⋅ Y is a dead marking, i.e. 0 ≤ ( M 0 + C ⋅ Y ) ( s i ) < a i 0 \le(M_0+C\cdot Y)(s_i)<a_i 0 ≤ ( M 0 + C ⋅ Y ) ( s i ) < a i for all i i i .
Proof. (1)⇒ \Rightarrow ⇒ (2): Suppose that some reachable marking D D D is dead. The only firing sequence from D D D is the empty one, so t 0 t_0 t 0 occurs in no firing sequence from D D D , and t 0 t_0 t 0 is not live. Hence ( N , M 0 ) (N,M_0) ( N , M 0 ) is not live.
(2)⇒ \Rightarrow ⇒ (4): Suppose that no reachable marking is dead. Since M 0 M_0 M 0 is reachable, some transition τ 1 \tau_1 τ 1 is enabled at M 0 M_0 M 0 ; let M 0 → τ 1 M ( 1 ) M_0 \xrightarrow{\tau_1} M^{(1)} M 0 τ 1 M ( 1 ) . The marking M ( 1 ) M^{(1)} M ( 1 ) is reachable, hence not dead, so some transition τ 2 \tau_2 τ 2 is enabled at M ( 1 ) M^{(1)} M ( 1 ) ; let M ( 1 ) → τ 2 M ( 2 ) M^{(1)} \xrightarrow{\tau_2} M^{(2)} M ( 1 ) τ 2 M ( 2 ) ; and so on. This yields an infinite firing sequence τ 1 τ 2 τ 3 ⋯ \tau_1\tau_2\tau_3\cdots τ 1 τ 2 τ 3 ⋯ from M 0 M_0 M 0 .
(4)⇒ \Rightarrow ⇒ (5): If ( N , M 0 ) (N,M_0) ( N , M 0 ) had a deadlock certificate, then by Lemma 3.1 there would be no infinite firing sequence from M 0 M_0 M 0 .
(5)⇒ \Rightarrow ⇒ (6): A vector Y Y Y as in (6) satisfies (3.1), i.e. it is a deadlock certificate. So if there is no deadlock certificate, there is no vector as in (6) either.
(6)⇒ \Rightarrow ⇒ (1): We show the contrapositive. Suppose that ( N , M 0 ) (N,M_0) ( N , M 0 ) is not live. Then there are a reachable marking M M M and a transition t i t_i t i such that t i t_i t i occurs in no firing sequence from M M M . By Lemma 3.2(b), a dead marking D D D is reachable from M M M , and hence from M 0 M_0 M 0 ; say M 0 → ρ D M_0 \xrightarrow{\rho} D M 0 ρ D . By the state equation, Y : = P ( ρ ) ∈ N n Y:=P(\rho)\in\mathbb{N}^{n} Y := P ( ρ ) ∈ N n satisfies M 0 + C ⋅ Y = D M_0+C\cdot Y=D M 0 + C ⋅ Y = D , which is a dead marking. So (6) fails.
(3)⇒ \Rightarrow ⇒ (4): Every transition is weakly live, so in particular some infinite firing sequence from M 0 M_0 M 0 exists (recall n ≥ 1 n\ge1 n ≥ 1 ).
(4)⇒ \Rightarrow ⇒ (3): By Lemma 3.2(a), every transition occurs infinitely often in an infinite firing sequence from M 0 M_0 M 0 ; so every transition is weakly live.
:::
As mentioned at the beginning of this section, the equivalences (1)⇔ \Leftrightarrow ⇔ (6) and (1)⇔ \Leftrightarrow ⇔ (5) are [18 Thm. 6.6 and Thm. 6.8] ; see [19 Cor. 6.7] for a generalisation.
Conditions (5) and (6) differ only in whether M 0 + C ⋅ Y ≥ 0 M_0+C\cdot Y\ge0 M 0 + C ⋅ Y ≥ 0 is required. Condition (6) speaks about vectors Y Y Y that lead, via the state equation, to an actual dead marking; condition (5) only asks that every place s i s_i s i carries fewer than a i a_i a i “tokens”, and allows negative entries. The implication (5)⇒ \Rightarrow ⇒ (6) is trivial; the converse holds by the lemma, but the proof goes through liveness. The proof of the upper bound below (Proposition 3.5 ) uses the form (6).
Lemmas 3.1 and 3.3 together show that a marking that is not live has essentially only one way of dying:
Corollary 3.4 (the dead marking is unique; cf. [18 Thm. 6.7] ). Suppose that M 0 M_0 M 0 is not live. Then ( N , M 0 ) (N,M_0) ( N , M 0 ) has a least deadlock certificate Y min Y_{\min} Y m i n , i.e. a deadlock certificate with Y min ≤ Y Y_{\min}\le Y Y m i n ≤ Y for every deadlock certificate Y Y Y . Every maximal firing sequence from M 0 M_0 M 0 is finite, has the Parikh vector Y min Y_{\min} Y m i n , and ends in the dead marking M 0 + C ⋅ Y min M_0+C\cdot Y_{\min} M 0 + C ⋅ Y m i n ; in particular, this is the only dead marking reachable from M 0 M_0 M 0 .
Idea. By Lemma 3.1, the Parikh vector of every firing sequence from M 0 M_0 M 0 is bounded by every deadlock certificate. The Parikh vector of a maximal firing sequence is itself a deadlock certificate, so it is the least one, and therefore the same for all maximal firing sequences.
Proof. Let ρ \rho ρ be a maximal firing sequence from M 0 M_0 M 0 (one always exists: fire enabled transitions as long as possible). Since M 0 M_0 M 0 is not live, there is no infinite firing sequence from M 0 M_0 M 0 , by Lemma 3.3, (4)⇒ \Rightarrow ⇒ (1); so ρ \rho ρ , like every maximal firing sequence from M 0 M_0 M 0 , is finite and leads to a dead marking, say M 0 → ρ D M_0 \xrightarrow{\rho} D M 0 ρ D . By the state equation, D = M 0 + C ⋅ P ( ρ ) D=M_0+C\cdot\mathcal{P}(\rho) D = M 0 + C ⋅ P ( ρ ) , so P ( ρ ) \mathcal{P}(\rho) P ( ρ ) is a deadlock certificate, and P ( ρ ) ≤ Y \mathcal{P}(\rho)\leq Y P ( ρ ) ≤ Y for every deadlock certificate Y Y Y , by Lemma 3.1. If ρ ′ \rho' ρ ′ is another maximal firing sequence from M 0 M_0 M 0 , then likewise P ( ρ ′ ) ≤ P ( ρ ) \mathcal{P}(\rho')\leq\mathcal{P}(\rho) P ( ρ ′ ) ≤ P ( ρ ) and P ( ρ ) ≤ P ( ρ ′ ) \mathcal{P}(\rho)\leq\mathcal{P}(\rho') P ( ρ ) ≤ P ( ρ ′ ) , i.e. P ( ρ ′ ) = P ( ρ ) \mathcal{P}(\rho')=\mathcal{P}(\rho) P ( ρ ′ ) = P ( ρ ) . So Y min : = P ( ρ ) Y_{\min}:=\mathcal{P}(\rho) Y m i n := P ( ρ ) has all the stated properties. Finally, every dead marking reachable from M 0 M_0 M 0 is reached by a maximal firing sequence.
So, whatever choices are made, a ring started at a marking that is not live always stops in the same dead marking, after the same numbers of occurrences of each transition. Chip-firing games have the same property (§ 5 ).
Proposition 3.5 (upper bound; cf. [18 , 19 ] ). RingLive is in coNP .
Proof. We show that the complement of RingLive is in NP. By Lemma 3.3, (1)⇔ \Leftrightarrow ⇔ (6), M 0 M_0 M 0 is not live iff there is Y ∈ N n Y\in\mathbb{N}^n Y ∈ N n such that D : = M 0 + C ⋅ Y D:=M_0+C\cdot Y D := M 0 + C ⋅ Y satisfies 0 ≤ D ( s i ) ≤ a i − 1 0\leq D(s_i)\leq a_i-1 0 ≤ D ( s i ) ≤ a i − 1 for all i i i . With a vector Z ∈ N n Z\in\mathbb{N}^n Z ∈ N n of slack variables, this is the existence of a solution of the integer linear system
D − C ⋅ Y = M 0 , D + Z = ( a 0 − 1 , a 1 − 1 , … , a n − 1 − 1 ) , D , Y , Z ∈ N n , D-C\cdot Y=M_0,\qquad D+Z=(a_0-1,a_1-1,\ldots,a_{n-1}-1),\qquad D,Y,Z\in\mathbb{N}^n, D − C ⋅ Y = M 0 , D + Z = ( a 0 − 1 , a 1 − 1 , … , a n − 1 − 1 ) , D , Y , Z ∈ N n , a system of the form A v = c Av=c A v = c , v ∈ N q v\in\mathbb{N}^q v ∈ N q , with p = 2 n p=2n p = 2 n equations and q = 3 n q=3n q = 3 n unknowns v = ( D , Y , Z ) v=(D,Y,Z) v = ( D , Y , Z ) . The entries of the p × q p\times q p × q matrix A A A are 0 0 0 , ± 1 \pm1 ± 1 and the entries of − C -C − C , and the entries of c c c are the numbers M 0 ( s i ) M_0(s_i) M 0 ( s i ) and a i − 1 a_i-1 a i − 1 ; let w w w be the largest absolute value of all these numbers. By the theorem of Papadimitriou [24 Theorem, p. 767] , if a system A v = c Av=c A v = c with p p p equations and q q q unknowns, all of whose coefficients have absolute value at most w w w , has a solution v ∈ N q v\in\mathbb{N}^q v ∈ N q , then it has one with all entries at most q ( p w ) 2 p + 1 q(pw)^{2p+1} q ( pw ) 2 p + 1 . This bound has O ( n log ( n w ) ) O(n\log(nw)) O ( n log ( n w )) bits, which is polynomial in the size of the instance, because log w \log w log w is at most the number of bits of the largest number in it. Hence M 0 M_0 M 0 is not live iff there is a vector Y ∈ N n Y\in\mathbb{N}^n Y ∈ N n whose entries have polynomially many bits such that 0 ≤ M 0 + C ⋅ Y < ( a 0 , a 1 , … , a n − 1 ) 0\leq M_0+C\cdot Y<(a_0,a_1,\ldots,a_{n-1}) 0 ≤ M 0 + C ⋅ Y < ( a 0 , a 1 , … , a n − 1 ) . A nondeterministic algorithm can guess such a Y Y Y and check the condition in polynomial time, by computing the n n n numbers ( M 0 + C ⋅ Y ) ( s i ) (M_0+C\cdot Y)(s_i) ( M 0 + C ⋅ Y ) ( s i ) using (2.2). So the complement of RingLive is in NP, i.e. RingLive is in coNP.
Bounds of this kind on small nonnegative integer solutions of linear systems go back to Borosh and Treybig [6 ] and von zur Gathen and Sieveking [17 ] ; we use Papadimitriou’s form because it is stated for equations A v = c Av=c A v = c with v ≥ 0 v\geq0 v ≥ 0 and gives an explicit bound.
Example 3.6 (running example, continued). In Example 2.2, ( C ⋅ Y ) ( s 0 ) = − 2 ( Y 0 − 2 Y 1 ) (C\cdot Y)(s_0)=-2(Y_0-2Y_1) ( C ⋅ Y ) ( s 0 ) = − 2 ( Y 0 − 2 Y 1 ) and ( C ⋅ Y ) ( s 1 ) = 3 ( Y 0 − 2 Y 1 ) (C\cdot Y)(s_1)=3(Y_0-2Y_1) ( C ⋅ Y ) ( s 1 ) = 3 ( Y 0 − 2 Y 1 ) ; so C ⋅ Y C\cdot Y C ⋅ Y depends only on d : = Y 0 − 2 Y 1 d:=Y_0-2Y_1 d := Y 0 − 2 Y 1 . Consider the marking M 0 = ( c , 0 ) M_0=(c,0) M 0 = ( c , 0 ) with c ∈ N c\in\mathbb{N} c ∈ N . A vector Y ∈ N 2 Y\in\mathbb{N}^2 Y ∈ N 2 is a deadlock certificate for ( N , M 0 ) (N,M_0) ( N , M 0 ) iff
c − 2 d < 2 and 3 d < 6 , i.e. c − 2 2 < d ≤ 1. c-2d<2\qquad\text{and}\qquad3d<6,\qquad\text{i.e.}\qquad\frac{c-2}{2}<d\leq1. c − 2 d < 2 and 3 d < 6 , i.e. 2 c − 2 < d ≤ 1. For c ≥ 4 c\geq4 c ≥ 4 no integer d d d satisfies this, so ( c , 0 ) (c,0) ( c , 0 ) is live by Lemma 3.3, as observed for c = 4 c=4 c = 4 in Example 2.2. For c ≤ 3 c\leq3 c ≤ 3 , the value d = 1 d=1 d = 1 satisfies it: every Y ∈ N 2 Y\in\mathbb{N}^2 Y ∈ N 2 with Y 0 − 2 Y 1 = 1 Y_0-2Y_1=1 Y 0 − 2 Y 1 = 1 , for instance Y = ( 1 , 0 ) Y=(1,0) Y = ( 1 , 0 ) or Y = ( 3 , 1 ) Y=(3,1) Y = ( 3 , 1 ) , is a deadlock certificate, and ( c , 0 ) (c,0) ( c , 0 ) is not live. For such Y Y Y , M 0 + C ⋅ Y = ( c − 2 , 3 ) M_0+C\cdot Y=(c-2,3) M 0 + C ⋅ Y = ( c − 2 , 3 ) . For c ∈ { 2 , 3 } c\in\{2,3\} c ∈ { 2 , 3 } this is a dead marking; for c = 3 c=3 c = 3 it is the dead marking ( 1 , 3 ) (1,3) ( 1 , 3 ) found in Example 2.2, and Lemma 3.1 with Y = ( 1 , 0 ) Y=(1,0) Y = ( 1 , 0 ) confirms that from ( 3 , 0 ) (3,0) ( 3 , 0 ) , t 0 t_0 t 0 can occur at most once and t 1 t_1 t 1 not at all. For c ∈ { 0 , 1 } c\in\{0,1\} c ∈ { 0 , 1 } , the vector ( c − 2 , 3 ) (c-2,3) ( c − 2 , 3 ) has a negative entry, so
Y = ( 1 , 0 ) Y = (1,0) Y = ( 1 , 0 ) is a deadlock certificate in the sense of (5) but does not satisfy (6); for these c c c , the vector Y = ( 0 , 0 ) Y = (0,0) Y = ( 0 , 0 ) satisfies (6), since ( c , 0 ) (c,0) ( c , 0 ) is dead itself. In accordance with Corollary 3.4, the least deadlock certificate is Y min = ( 1 , 0 ) Y_{\min} = (1,0) Y m i n = ( 1 , 0 ) for c ∈ { 2 , 3 } c \in\{2,3\} c ∈ { 2 , 3 } , the Parikh vector of the only maximal firing sequence t 0 t_0 t 0 , and Y min = ( 0 , 0 ) Y_{\min} = (0,0) Y m i n = ( 0 , 0 ) for c ∈ { 0 , 1 } c \in\{0,1\} c ∈ { 0 , 1 } , where the only maximal firing sequence is the empty one.
Remark 3.7 (more tokens never hurt). Firing is monotone [1 Lemma 1.13] : if M → σ M ′ M \xrightarrow{\sigma} M' M σ M ′ and K K K is any marking, then M + K → σ M ′ + K M + K \xrightarrow{\sigma} M' + K M + K σ M ′ + K , because additional tokens never prevent a transition from being enabled and are not touched when it fires; the same holds for infinite firing sequences, prefix by prefix. By Lemma 3.3, a marking of a ring is live iff some infinite firing sequence starts at it. Hence, if M M M is a live marking of a ring N N N , then every marking M ′ ≥ M M' \ge M M ′ ≥ M of N N N is live as well. So the set of live markings of a ring is upward closed ; by Dickson’s lemma, it has only finitely many minimal elements, and it consists of the markings that are greater than or equal to one of them. In general Petri nets, in contrast, adding tokens can destroy liveness [1 Sect. 5.1 and Exercise 5.5] .
The lower bound
In this section we show that RingLive is coNP-hard, even in the strong sense. The reduction starts from the covering problem for residue classes (Definition 4.1), which is coNP-complete (Proposition 4.2). For a covering instance I I I we construct a token-conserving marked ring R ( I , W ) R(I,W) R ( I , W ) (Construction 4.3) and show that it is live iff I I I covers Z \mathbb{Z} Z (Lemma 4.4). Example 4.5 illustrates the construction on two small instances, and Theorem 4.6 puts the pieces together. Finally, Corollary 4.9 extends the result to weighted T-systems.
Definition 4.1 (covering). A covering instance is a list I = ( ( r 0 , b 0 ) , ( r 1 , b 1 ) , … , ( r m − 1 , b m − 1 ) ) I = ((r_0,b_0),(r_1,b_1),\ldots,(r_{m-1},b_{m-1})) I = (( r 0 , b 0 ) , ( r 1 , b 1 ) , … , ( r m − 1 , b m − 1 )) of m ≥ 1 m \ge1 m ≥ 1 pairs of integers with b i ≥ 1 b_i \ge1 b i ≥ 1 and 0 ≤ r i < b i 0 \le r_i < b_i 0 ≤ r i < b i . An integer x x x is covered by I I I if x ≡ r i ( m o d b i ) x \equiv r_i \pmod{b_i} x ≡ r i ( mod b i ) for some i i i ; I I I covers Z \mathbb{Z} Z if every integer is covered. Cover asks whether a given I I I covers Z \mathbb{Z} Z .
For instance, ( ( 0 , 2 ) , ( 1 , 2 ) ) ((0,2),(1,2)) (( 0 , 2 ) , ( 1 , 2 )) covers Z \mathbb{Z} Z (every integer is even or odd), and so does ( ( 0 , 2 ) , ( 1 , 4 ) , ( 3 , 4 ) ) ((0,2),(1,4),(3,4)) (( 0 , 2 ) , ( 1 , 4 ) , ( 3 , 4 )) : an odd integer leaves the remainder 1 or 3 when divided by 4. In contrast, ( ( 0 , 2 ) , ( 1 , 4 ) ) ((0,2),(1,4)) (( 0 , 2 ) , ( 1 , 4 )) does not cover Z \mathbb{Z} Z , since the integers x x x with x m o d 4 = 3 x \bmod4 = 3 x mod 4 = 3 are not covered. A less obvious covering, due to Erdős [13 ] , consists of the classes 0 mod 2, 0 mod 3, 1 mod 4, 5 mod 6 and 7 mod 12.
For a covering instance I I I as above, let B : = lcm ( b 0 , b 1 , … , b m − 1 ) B := \operatorname{lcm}(b_0,b_1,\ldots,b_{m-1}) B := lcm ( b 0 , b 1 , … , b m − 1 ) . Since every b i b_i b i divides B B B , two integers x ≡ x ′ ( m o d B ) x \equiv x' \pmod B x ≡ x ′ ( mod B ) satisfy x ≡ x ′ ( m o d b i ) x \equiv x' \pmod{b_i} x ≡ x ′ ( mod b i ) for every i i i , so x x x is covered by I I I iff x ′ x' x ′ is. In particular,
I covers Z ⟺ every x ∈ { 0 , 1 , … , B − 1 } is covered by I . (4) I \text{ covers } \mathbb{Z} \quad\Longleftrightarrow\quad\text{every } x \in\{0,1,\ldots,B-1\} \text{ is covered by } I. \tag*{(4)} I covers Z ⟺ every x ∈ { 0 , 1 , … , B − 1 } is covered by I . (4)
The complement of Cover is Simultaneous Incongruences [16 AN2] . The idea of encoding truth assignments by residues modulo distinct primes goes back to Stockmeyer and Meyer [25 ] , who used it to show that universality of regular expressions over a one-letter alphabet is coNP-complete; the residue class r m o d b r \bmod b r mod b corresponds to the expression 0 r ( 0 b ) ∗ 0^r(0^b)^* 0 r ( 0 b ) ∗ . Problems about residue classes of this kind also underlie the (strong) coNP-hardness of deciding the feasibility of periodic real-time task systems with release offsets [20 , 5 ] . We give a self-contained proof for residue classes, which also records that the moduli stay small.
Recall that a literal is a Boolean variable X X X or its negation ¬ X \neg X ¬ X , a clause is a disjunction of literals, and a 3-CNF formula is a conjunction of clauses, each consisting of three literals.
Proposition 4.2 (cf. [25 ] , [16 AN2] ). Cover is coNP-complete . More precisely, let p j p_j p j denote the j j j -th odd prime (p 1 = 3 p_1 = 3 p 1 = 3 , p 2 = 5 p_2 = 5 p 2 = 5 , p 3 = 7 , … p_3 = 7,\ldots p 3 = 7 , … ). There is a polynomial-time reduction mapping each 3-CNF formula φ \varphi φ that has at least one clause and whose clauses consist of three literals
over three distinct variables, with k k k variables and l l l clauses, to a covering instance I ( φ ) I(\varphi) I ( φ ) with m = l + ∑ j = 1 k ( p j − 2 ) m = l + \sum_{j=1}^{k}(p_j - 2) m = l + ∑ j = 1 k ( p j − 2 ) pairs, all of whose moduli are at most p k 3 = O ( k 3 log 3 k ) p_k^3 = O(k^3 \log^3 k) p k 3 = O ( k 3 log 3 k ) , such that φ \varphi φ is unsatisfiable iff I ( φ ) I(\varphi) I ( φ ) covers Z \mathbb{Z} Z .
Proof. Membership in coNP. If I I I does not cover Z \mathbb{Z} Z , then by (4) some x ∈ { 0 , 1 , … , B − 1 } x \in\{0,1,\ldots,B-1\} x ∈ { 0 , 1 , … , B − 1 } is uncovered. Since B B B is at most the product b 0 b 1 ⋯ b m − 1 b_0b_1\cdots b_{m-1} b 0 b 1 ⋯ b m − 1 , the binary representation of x x x is not longer than the binary representations of b 0 , b 1 , … , b m − 1 b_0,b_1,\ldots,b_{m-1} b 0 , b 1 , … , b m − 1 together, and one can check in polynomial time that x ≢ r i ( m o d b i ) x \not\equiv r_i \pmod{b_i} x ≡ r i ( mod b i ) for all i i i . So such an x x x is a certificate of polynomial size for non-covering.
Normal form of the formulas. 3-SAT remains NP-complete for formulas that have at least one clause and whose clauses consist of three literals over three distinct variables. Indeed, a clause containing a variable together with its negation is satisfied by every assignment and can be deleted, and a clause with fewer than three distinct literals can be padded with new variables without changing satisfiability: ( ℓ 1 ∨ ℓ 2 ) (\ell_1 \lor\ell_2) ( ℓ 1 ∨ ℓ 2 ) is replaced by ( ℓ 1 ∨ ℓ 2 ∨ Z ) ∧ ( ℓ 1 ∨ ℓ 2 ∨ ¬ Z ) (\ell_1 \lor\ell_2 \lor Z) \land(\ell_1 \lor\ell_2 \lor\neg Z) ( ℓ 1 ∨ ℓ 2 ∨ Z ) ∧ ( ℓ 1 ∨ ℓ 2 ∨ ¬ Z ) , and ( ℓ 1 ) (\ell_1) ( ℓ 1 ) by the four clauses ( ℓ 1 ∨ ± Z 1 ∨ ± Z 2 ) (\ell_1 \lor\pm Z_1 \lor\pm Z_2) ( ℓ 1 ∨ ± Z 1 ∨ ± Z 2 ) , where Z Z Z , Z 1 Z_1 Z 1 , Z 2 Z_2 Z 2 are new variables. A formula without clauses is satisfiable and can be replaced by the single clause ( Z 1 ∨ Z 2 ∨ Z 3 ) (Z_1 \lor Z_2 \lor Z_3) ( Z 1 ∨ Z 2 ∨ Z 3 ) over three new variables. In particular, such a formula has k ≥ 3 k \ge3 k ≥ 3 variables, and the instance I ( φ ) I(\varphi) I ( φ ) constructed below has m ≥ 1 m \ge1 m ≥ 1 pairs. Finally, repeated clauses can be deleted, so 3-SAT remains NP-complete also for formulas of this form without repeated clauses.
The reduction. Let φ \varphi φ be such a formula. Its variables are X 1 , X 2 , … , X k X_1,X_2,\ldots,X_k X 1 , X 2 , … , X k , and its clauses are c 1 , c 2 , … , c l c_1,c_2,\ldots,c_l c 1 , c 2 , … , c l . For a clause c c c over the variables X j 1 , X j 2 , X j 3 X_{j_1},X_{j_2},X_{j_3} X j 1 , X j 2 , X j 3 (with j 1 , j 2 , j 3 j_1,j_2,j_3 j 1 , j 2 , j 3 distinct), let ( f 1 c , f 2 c , f 3 c ) ∈ { 0 , 1 } 3 (f^c_1,f^c_2,f^c_3) \in\{0,1\}^3 ( f 1 c , f 2 c , f 3 c ) ∈ { 0 , 1 } 3 be the unique assignment to these three variables that falsifies c c c , writing 1 for true and 0 for false: f t c = 0 f^c_t=0 f t c = 0 if X j t X_{j_t} X j t occurs positively in c c c , and f t c = 1 f^c_t=1 f t c = 1 if it occurs negatively. Then I ( φ ) I(\varphi) I ( φ ) consists of the following pairs:
the pairs ( ρ , p j ) (\rho,p_j) ( ρ , p j ) for 1 ≤ j ≤ k 1 \le j \le k 1 ≤ j ≤ k and 2 ≤ ρ ≤ p j − 1 2 \le\rho\le p_j-1 2 ≤ ρ ≤ p j − 1 ;
for each clause c c c as above, the pair ( ρ c , q c ) (\rho_c,q_c) ( ρ c , q c ) , where q c : = p j 1 p j 2 p j 3 q_c := p_{j_1}p_{j_2}p_{j_3} q c := p j 1 p j 2 p j 3 and ρ c \rho_c ρ c is the unique integer in [ 0 , q c ) [0,q_c) [ 0 , q c ) with ρ c ≡ f t c ( m o d p j t ) \rho_c \equiv f^c_t \pmod{p_{j_t}} ρ c ≡ f t c ( mod p j t ) for t = 1 , 2 , 3 t=1,2,3 t = 1 , 2 , 3 ; it exists by the Chinese remainder theorem, since p j 1 , p j 2 , p j 3 p_{j_1},p_{j_2},p_{j_3} p j 1 , p j 2 , p j 3 are distinct primes.
Size and running time. Group (i) has p j − 2 ≥ 1 p_j-2 \ge1 p j − 2 ≥ 1 pairs for each j j j , and group (ii) has l l l pairs, so m = l + ∑ j = 1 k ( p j − 2 ) m = l + \sum_{j=1}^{k}(p_j-2) m = l + ∑ j = 1 k ( p j − 2 ) . All moduli are at most p k 3 p_k^3 p k 3 , and p k = O ( k log k ) p_k = O(k \log k) p k = O ( k log k ) by the prime number theorem. The primes p 1 , p 2 , … , p k p_1,p_2,\ldots,p_k p 1 , p 2 , … , p k can be found by trial division, and each ρ c \rho_c ρ c by the extended Euclidean algorithm, so I ( φ ) I(\varphi) I ( φ ) can be computed in time polynomial in k + l k+l k + l .
Correctness. We use the following consequence of the Chinese remainder theorem: for every integer x x x and every clause c c c over X j 1 , X j 2 , X j 3 X_{j_1},X_{j_2},X_{j_3} X j 1 , X j 2 , X j 3 ,
x ≡ ρ c ( m o d q c ) ⟺ x m o d p j t = f t c for t = 1 , 2 , 3. (5) x \equiv\rho_c \pmod{q_c} \quad\Longleftrightarrow\quad x \bmod p_{j_t}=f^c_t \text{ for } t=1,2,3. \tag*{(5)} x ≡ ρ c ( mod q c ) ⟺ x mod p j t = f t c for t = 1 , 2 , 3. (5)
Indeed, since q c q_c q c is the product of the distinct primes p j 1 , p j 2 , p j 3 p_{j_1},p_{j_2},p_{j_3} p j 1 , p j 2 , p j 3 , we have x ≡ ρ c ( m o d q c ) x \equiv\rho_c \pmod{q_c} x ≡ ρ c ( mod q c ) iff x ≡ ρ c ≡ f t c ( m o d p j t ) x \equiv\rho_c \equiv f^c_t \pmod{p_{j_t}} x ≡ ρ c ≡ f t c ( mod p j t ) for t = 1 , 2 , 3 t=1,2,3 t = 1 , 2 , 3 , and 0 ≤ f t c < p j t 0 \le f^c_t < p_{j_t} 0 ≤ f t c < p j t .
Suppose first that some integer x x x is not covered by I ( φ ) I(\varphi) I ( φ ) . Since x x x is not covered by the pairs (i), x m o d p j < 2 x \bmod p_j < 2 x mod p j < 2 , i.e. x m o d p j ∈ { 0 , 1 } x \bmod p_j \in\{0,1\} x mod p j ∈ { 0 , 1 } , for every j j j . Let A A A be the assignment with A ( X j ) : = x m o d p j A(X_j):=x \bmod p_j A ( X j ) := x mod p j . Since x x x is not covered by the pairs (ii), (5) shows that for every clause c c c the values of A A A on the variables of c c c differ from ( f 1 c , f 2 c , f 3 c ) (f^c_1,f^c_2,f^c_3) ( f 1 c , f 2 c , f 3 c ) , so A A A does not falsify c c c . Hence A A A satisfies φ \varphi φ .
Conversely, let A A A be a satisfying assignment, with values in { 0 , 1 } \{0,1\} { 0 , 1 } . By the Chinese remainder theorem there is an integer x x x with x ≡ A ( X j ) ( m o d p j ) x \equiv A(X_j) \pmod{p_j} x ≡ A ( X j ) ( mod p j ) for all j j j . Then x m o d p j = A ( X j ) ∈ { 0 , 1 } x \bmod p_j=A(X_j)\in\{0,1\} x mod p j = A ( X j ) ∈ { 0 , 1 } , so x x x is not covered by the pairs (i); and since A A A falsifies no clause, (5) shows that x x x is not covered by the pairs (ii).
Thus φ \varphi φ is satisfiable iff some integer is not covered by I ( φ ) I(\varphi) I ( φ ) , i.e. φ \varphi φ is unsatisfiable iff I ( φ ) I(\varphi) I ( φ ) covers Z \mathbb{Z} Z . Since 3-SAT is NP-complete, COVER is coNP-hard. ▫
From covering instances to rings. We now come to the core of the reduction. By Proposition 4.2 , it suffices to transform each covering instance I = ( ( r 0 , b 0 ) , ( r 1 , b 1 ) , … , ( r m − 1 , b m − 1 ) ) I = ((r_0, b_0),(r_1, b_1), \ldots,(r_{m-1}, b_{m-1})) I = (( r 0 , b 0 ) , ( r 1 , b 1 ) , … , ( r m − 1 , b m − 1 )) , in polynomial time and with polynomially bounded numbers, into a marked ring that is live iff I I I covers Z \mathbb{Z} Z . Recall from § 2 that in a ring, the transition t i t_i t i takes a i a_i a i tokens from s i s_i s i and puts b i b_i b i tokens on s i + 1 s_{i+1} s i + 1 , and that the ring is token-conserving if a i = b i a_i = b_i a i = b i for all i i i ; by Lemma 3.3 , a marked ring is live iff it has an infinite firing sequence. The ring R ( I , W ) R(I,W) R ( I , W ) constructed below is token-conserving; its weights are the moduli of I I I and a number W W W that is larger than all moduli and coprime to them. It has one pair of places u i , v i u_i,v_i u i , v i for each pair ( r i , b i ) (r_i,b_i) ( r i , b i ) of I I I . Together, these pairs act as a counter z z z that can advance from z z z to z + 1 z+1 z + 1 iff W z Wz W z is covered by I I I , as explained after the construction. So the ring runs forever iff all the numbers 0 , W , 2 W , 3 W , … 0,W,2W,3W,\ldots 0 , W , 2 W , 3 W , … are covered, and because W W W is coprime to all moduli, this holds iff I I I covers Z \mathbb{Z} Z .
Construction 4.3 (the marked ring R ( I , W ) R(I,W) R ( I , W ) ). Let I = ( ( r 0 , b 0 ) , ( r 1 , b 1 ) , … , ( r m − 1 , b m − 1 ) ) I = ((r_0, b_0),(r_1, b_1), \ldots,(r_{m-1}, b_{m-1})) I = (( r 0 , b 0 ) , ( r 1 , b 1 ) , … , ( r m − 1 , b m − 1 )) be a covering instance and let W W W be an integer with W > max i b i W > \max_i b_i W > max i b i and gcd ( W , b i ) = 1 \gcd(W,b_i) = 1 g cd( W , b i ) = 1 for all i i i (for instance, a prime W > max i b i W > \max_i b_i W > max i b i ). Put r ˉ i : = ( − r i ) m o d b i \bar{r}_i := (-r_i) \bmod b_i r ˉ i := ( − r i ) mod b i ; thus 0 ≤ r ˉ i < b i 0 \le\bar{r}_i < b_i 0 ≤ r ˉ i < b i and r ˉ i ≡ − r i ( m o d b i ) \bar{r}_i \equiv-r_i \pmod{b_i} r ˉ i ≡ − r i ( mod b i ) . The underlying ring net has the 2 m 2m 2 m places u 0 , v 0 , u 1 , v 1 , … , u m − 1 , v m − 1 u_0,v_0,u_1,v_1,\ldots,u_{m-1},v_{m-1} u 0 , v 0 , u 1 , v 1 , … , u m − 1 , v m − 1 , in this cyclic order, and the set T T T of 2 m 2m 2 m transitions α 0 , β 0 , α 1 , β 1 , … , α m − 1 , β m − 1 \alpha_0,\beta_0,\alpha_1,\beta_1,\ldots,\alpha_{m-1},\beta_{m-1} α 0 , β 0 , α 1 , β 1 , … , α m − 1 , β m − 1 :
α i \alpha_i α i takes b i b_i b i tokens from u i u_i u i and puts b i b_i b i tokens on v i v_i v i ;
β i \beta_i β i takes W W W tokens from v i v_i v i and puts W W W tokens on u i + 1 u_{i+1} u i + 1 (where u m = u 0 u_m = u_0 u m = u 0 ).
Its initial marking M 0 M_0 M 0 is given by M 0 ( u i ) = r ˉ i M_0(u_i) = \bar{r}_i M 0 ( u i ) = r ˉ i and M 0 ( v i ) = W − r ˉ i M_0(v_i) = W-\bar{r}_i M 0 ( v i ) = W − r ˉ i ; both are non-negative, as r ˉ i < b i < W \bar{r}_i < b_i < W r ˉ i < b i < W . The marked ring R ( I , W ) R(I,W) R ( I , W ) is the pair of this ring net and M 0 M_0 M 0 ; so “R ( I , W ) R(I,W) R ( I , W ) is live” means that M 0 M_0 M 0 is live. The ring is token-conserving, and M 0 M_0 M 0 puts m W mW mW tokens on it in total. (In the notation of § 2 , with s 2 i = u i s_{2i}=u_i s 2 i = u i , s 2 i + 1 = v i s_{2i+1}=v_i s 2 i + 1 = v i , t 2 i = α i t_{2i}=\alpha_i t 2 i = α i and t 2 i + 1 = β i t_{2i+1}=\beta_i t 2 i + 1 = β i , both arc weights of α i \alpha_i α i are b i b_i b i and both arc weights of β i \beta_i β i are W W W .) Indices of u i , v i , α i , β i u_i,v_i,\alpha_i,\beta_i u i , v i , α i , β i are taken modulo m m m , as for rings in § 2 ; for instance, β − 1 = β m − 1 \beta_{-1}=\beta_{m-1} β − 1 = β m − 1 is the input transition of u 0 u_0 u 0 .
How the ring works. Look at one pair of places u i , v i u_i,v_i u i , v i . Initially it holds W W W tokens. Each occurrence of β i − 1 \beta_{i-1} β i − 1 brings W W W more tokens to u i u_i u i , each occurrence of β i \beta_i β i takes W W W tokens from v i v_i v i , and α i \alpha_i α i only moves tokens inside the pair, from u i u_i u i to v i v_i v i , b i b_i b i at a time. Suppose that β i − 1 \beta_{i-1} β i − 1 and β i \beta_i β i have both occurred z z z times, and α i \alpha_i α i as often as it could. Then the pair holds W W W tokens again. The place u i u_i u i has received r ˉ i + W z \bar{r}_i+Wz r ˉ i + W z tokens in total and has passed them on in groups of b i b_i b i , so it holds the remainder ( r ˉ i + W z ) m o d b i (\bar{r}_i+Wz)\bmod b_i ( r ˉ i + W z ) mod b i , and v i v_i v i holds the other W − ( r ˉ i + W z ) m o d b i W-(\bar{r}_i+Wz)\bmod b_i W − ( r ˉ i + W z ) mod b i tokens. Hence β i \beta_i β i can occur for the ( z + 1 ) (z+1) ( z + 1 ) -st time iff this remainder is 0 0 0 , i.e. iff W z ≡ r ˉ i ( m o d b i ) Wz\equiv\bar{r}_i\pmod{b_i} W z ≡ r ˉ i ( mod b i ) : the pair u i , v i u_i,v_i u i , v i tests whether W z Wz W z lies in the residue class r i m o d b i r_i\bmod b_i r i mod b i of I I I . So the common number z z z of occurrences of the transitions β j \beta_j β j acts as a counter, which can advance from z z z to z + 1 z+1 z + 1 iff W z Wz W z is covered by I I I . Lemma 4.4 below makes this precise.
Let C C C be the incidence matrix of R ( I , W ) R(I,W) R ( I , W ) . Place u i u_i u i gains W W W tokens with each occurrence of β i − 1 \beta_{i-1} β i − 1 and loses b i b_i b i tokens with each occurrence of α i \alpha_i α i ; place v i v_i v i gains b i b_i b i tokens with each occurrence of α i \alpha_i α i and loses W W W tokens with each occurrence of β i \beta_i β i . So, by (2) , for every Y ∈ Z T Y\in\mathbb{Z}^T Y ∈ Z T and every i ∈ { 0 , 1 , … , m − 1 } i\in\{0,1,\ldots,m-1\} i ∈ { 0 , 1 , … , m − 1 } ,
( C ⋅ Y ) ( u i ) = W Y ( β i − 1 ) − b i Y ( α i ) , ( C ⋅ Y ) ( v i ) = b i Y ( α i ) − W Y ( β i ) . (6) (C\cdot Y)(u_i)=WY(\beta_{i-1})-b_iY(\alpha_i),\qquad(C\cdot Y)(v_i)=b_iY(\alpha_i)-WY(\beta_i). \tag*{(6)} ( C ⋅ Y ) ( u i ) = W Y ( β i − 1 ) − b i Y ( α i ) , ( C ⋅ Y ) ( v i ) = b i Y ( α i ) − W Y ( β i ) . (6)
For z ∈ N z\in\mathbb{N} z ∈ N define Y z ∈ N T Y_z\in\mathbb{N}^T Y z ∈ N T by
Y z ( β i ) = z , Y z ( α i ) = ⌊ r ˉ i + W z b i ⌋ ( 0 ≤ i ≤ m − 1 ) , Y_z(\beta_i)=z,\qquad Y_z(\alpha_i)=\left\lfloor\frac{\bar{r}_i+Wz}{b_i}\right\rfloor\qquad(0\le i\le m-1), Y z ( β i ) = z , Y z ( α i ) = ⌊ b i r ˉ i + W z ⌋ ( 0 ≤ i ≤ m − 1 ) ,
and let D z : = M 0 + C ⋅ Y z D_z:=M_0+C\cdot Y_z D z := M 0 + C ⋅ Y z . Since Y z ( β i − 1 ) = Y z ( β i ) = z Y_z(\beta_{i-1})=Y_z(\beta_i)=z Y z ( β i − 1 ) = Y z ( β i ) = z , (4.3) gives, for 0 ≤ i ≤ m − 1 0\le i\le m-1 0 ≤ i ≤ m − 1 ,
D z ( u i ) = r ˉ i + W z − b i ⌊ r ˉ i + W z b i ⌋ = ( r ˉ i + W z ) m o d b i , D z ( v i ) = W − r ˉ i − W z + b i ⌊ r ˉ i + W z b i ⌋ = W − D z ( u i ) . (7) \begin{aligned}
D_z(u_i)&=\bar{r}_i+Wz-b_i\left\lfloor\frac{\bar{r}_i+Wz}{b_i}\right\rfloor=(\bar{r}_i+Wz)\bmod b_i,\\
D_z(v_i)&=W-\bar{r}_i-Wz+b_i\left\lfloor\frac{\bar{r}_i+Wz}{b_i}\right\rfloor=W-D_z(u_i). \tag*{(7)}
\end{aligned} D z ( u i ) D z ( v i ) = r ˉ i + W z − b i ⌊ b i r ˉ i + W z ⌋ = ( r ˉ i + W z ) mod b i , = W − r ˉ i − W z + b i ⌊ b i r ˉ i + W z ⌋ = W − D z ( u i ) . (7)
So D z D_z D z is the marking described in the paragraph above: the state equation gives it when every β i \beta_i β i has occurred z z z times and every α i \alpha_i α i as often as possible.
Lemma 4.4 (key lemma). Let R = R ( I , W ) R = R(I,W) R = R ( I , W ) be as in Construction 4.3, and let z ∈ N z \in\mathbb{N} z ∈ N .
(a) D z D_z D z is a marking, and D 0 = M 0 D_0 = M_0 D 0 = M 0 . No α i \alpha_i α i is enabled at D z D_z D z , and β i \beta_i β i is enabled at D z D_z D z iff W z ≡ r i ( m o d b i ) Wz \equiv r_i \pmod{b_i} W z ≡ r i ( mod b i ) . In particular, D z D_z D z is dead iff W z Wz W z is not covered by I I I .
(b) If W z Wz W z is covered by I I I , then D z → σ D z + 1 D_z \xrightarrow{\sigma} D_{z+1} D z σ D z + 1 for some firing sequence σ \sigma σ in which every β j \beta_j β j occurs exactly once.
(c) R R R is live if and only if I I I covers Z \mathbb{Z} Z .
(d) If R R R is not live, then there is a least z ∈ N z \in\mathbb{N} z ∈ N such that W z Wz W z is not covered by I I I ; call it z ∗ z^* z ∗ . Every maximal firing sequence from M 0 M_0 M 0 is finite, has Parikh vector Y z ∗ Y_{z^*} Y z ∗ , and ends in the dead marking D z ∗ D_{z^*} D z ∗ .
Idea. This is the counter of the paragraph “How the ring works”. Part (a) describes the markings D z D_z D z , at which the counter shows z z z . Part (b) lets the counter advance by one round, in which the W W W tokens moved by one β i \beta_i β i are passed on around the ring, pair by pair. Part (c) follows directly, and part (d) adds, with Corollary 3.4, that every other order of firing ends in the same dead marking.
Proof. By (4.4), for every j ∈ { 0 , 1 , … , m − 1 } j \in\{0,1,\ldots,m-1\} j ∈ { 0 , 1 , … , m − 1 } the place u j u_j u j holds D z ( u j ) = ( r ˉ j + W z ) m o d b j D_z(u_j) = (\bar{r}_j + Wz) \bmod b_j D z ( u j ) = ( r ˉ j + W z ) mod b j tokens at D z D_z D z , and v j v_j v j holds D z ( v j ) = W − D z ( u j ) D_z(v_j) = W - D_z(u_j) D z ( v j ) = W − D z ( u j ) tokens. Since r ˉ j ≡ − r j ( m o d b j ) \bar{r}_j \equiv-r_j \pmod{b_j} r ˉ j ≡ − r j ( mod b j ) ,
D z ( u j ) = 0 ⟺ b j ∣ r ˉ j + W z ⟺ W z ≡ r j ( m o d b j ) . (8) D_z(u_j) = 0 \quad\Longleftrightarrow\quad b_j \mid\bar{r}_j + Wz \quad\Longleftrightarrow\quad Wz \equiv r_j \pmod{b_j}. \tag*{(8)} D z ( u j ) = 0 ⟺ b j ∣ r ˉ j + W z ⟺ W z ≡ r j ( mod b j ) . (8)
(a) Fix j ∈ { 0 , 1 , … , m − 1 } j \in\{0,1,\ldots,m-1\} j ∈ { 0 , 1 , … , m − 1 } . We have 0 ≤ D z ( u j ) ≤ b j − 1 0 \le D_z(u_j) \le b_j - 1 0 ≤ D z ( u j ) ≤ b j − 1 , and hence D z ( v j ) = W − D z ( u j ) ≥ W − b j + 1 > 0 D_z(v_j) = W - D_z(u_j) \ge W - b_j + 1 > 0 D z ( v j ) = W − D z ( u j ) ≥ W − b j + 1 > 0 , because W > b j W > b_j W > b j . So D z D_z D z is a marking. For z = 0 z = 0 z = 0 , we have Y 0 ( β j ) = 0 Y_0(\beta_j) = 0 Y 0 ( β j ) = 0 and Y 0 ( α j ) = ⌊ r ˉ j / b j ⌋ = 0 Y_0(\alpha_j) = \lfloor\bar{r}_j/b_j \rfloor= 0 Y 0 ( α j ) = ⌊ r ˉ j / b j ⌋ = 0 , because 0 ≤ r ˉ j < b j 0 \le\bar{r}_j < b_j 0 ≤ r ˉ j < b j ; so Y 0 = 0 Y_0 = \mathbf{0} Y 0 = 0 and D 0 = M 0 D_0 = M_0 D 0 = M 0 . The transition α j \alpha_j α j is not enabled at D z D_z D z , because u j u_j u j holds fewer than b j b_j b j tokens. The transition β j \beta_j β j is enabled at D z D_z D z iff v j v_j v j holds at least W W W tokens, i.e. iff W − D z ( u j ) ≥ W W-D_z(u_j)\ge W W − D z ( u j ) ≥ W , i.e. iff D z ( u j ) = 0 D_z(u_j)=0 D z ( u j ) = 0 ; by (8) , this means W z ≡ r j ( m o d b j ) Wz\equiv r_j\pmod{b_j} W z ≡ r j ( mod b j ) . Hence some transition is enabled at D z D_z D z iff W z Wz W z lies in one of the classes of I I I ; that is, D z D_z D z is dead iff W z Wz W z is not covered.
(b) Since W z Wz W z is covered, there is an i i i with W z ≡ r i ( m o d b i ) Wz\equiv r_i\pmod{b_i} W z ≡ r i ( mod b i ) , and β i \beta_i β i is enabled at D z D_z D z by (a). Starting at D z D_z D z , we fire the following round σ \sigma σ : first β i \beta_i β i ; then, for the pairs j = i + 1 , i + 2 , … , i + m − 1 j=i+1,i+2,\ldots,i+m-1 j = i + 1 , i + 2 , … , i + m − 1 (indices modulo m m m ) in this order, α j \alpha_j α j as often as possible and then β j \beta_j β j once; finally α i \alpha_i α i as often as possible. (For m = 1 m=1 m = 1 , the round consists of β 0 \beta_0 β 0 , followed by α 0 \alpha_0 α 0 as often as possible.) Every β j \beta_j β j occurs exactly once in σ \sigma σ .
Consider any pair j j j ; its places are touched only by β j − 1 \beta_{j-1} β j − 1 , α j \alpha_j α j and β j \beta_j β j . During the round, u j u_j u j receives W W W tokens once (from β j − 1 \beta_{j-1} β j − 1 ), v j v_j v j gives away W W W tokens once (by β j \beta_j β j ), and α j \alpha_j α j fires as often as possible after the W W W tokens have arrived on u j u_j u j . Before they arrive, u j u_j u j still holds its D z ( u j ) D_z(u_j) D z ( u j ) tokens, because only β j − 1 \beta_{j-1} β j − 1 and α j \alpha_j α j change the number of tokens on u j u_j u j , and α j \alpha_j α j fires only after β j − 1 \beta_{j-1} β j − 1 . So the α j \alpha_j α j -firings leave on u j u_j u j the remainder of D z ( u j ) + W D_z(u_j)+W D z ( u j ) + W modulo b j b_j b j , which is ( r ˉ j + W ( z + 1 ) ) m o d b j = D z + 1 ( u j ) (\bar r_j+W(z+1))\bmod b_j=D_{z+1}(u_j) ( r ˉ j + W ( z + 1 )) mod b j = D z + 1 ( u j ) , because D z ( u j ) ≡ r ˉ j + W z ( m o d b j ) D_z(u_j)\equiv\bar r_j+Wz\pmod{b_j} D z ( u j ) ≡ r ˉ j + W z ( mod b j ) . The pair holds W W W tokens at D z D_z D z and has received and given away W W W tokens each; so at the end, v j v_j v j holds W − D z + 1 ( u j ) = D z + 1 ( v j ) W-D_{z+1}(u_j)=D_{z+1}(v_j) W − D z + 1 ( u j ) = D z + 1 ( v j ) tokens. Hence σ \sigma σ leads to D z + 1 D_{z+1} D z + 1 , provided that all its firings are possible.
The α \alpha α -firings are possible by construction, and β i \beta_i β i can fire at D z D_z D z by (a). For j ≠ i j\ne i j = i , the transition β j \beta_j β j fires right after the α j \alpha_j α j -firings. At that moment the pair holds 2 W 2W 2 W tokens (its W W W tokens at D z D_z D z and the W W W tokens received), of which only D z + 1 ( u j ) < b j < W D_{z+1}(u_j)<b_j<W D z + 1 ( u j ) < b j < W lie on u j u_j u j ; so v j v_j v j holds more than W W W tokens, and β j \beta_j β j is enabled. Hence D z → σ D z + 1 D_z\xrightarrow{\sigma}D_{z+1} D z σ D z + 1 .
(c) Suppose first that I I I covers Z \mathbb{Z} Z . Then every W z Wz W z is covered, and (b) gives rounds D 0 → σ 0 D 1 → σ 1 D 2 → σ 2 ⋯ D_0\xrightarrow{\sigma_0}D_1\xrightarrow{\sigma_1}D_2\xrightarrow{\sigma_2}\cdots D 0 σ 0 D 1 σ 1 D 2 σ 2 ⋯ . Since D 0 = M 0 D_0=M_0 D 0 = M 0 by (a), the infinite word σ 0 σ 1 σ 2 ⋯ \sigma_0\sigma_1\sigma_2\cdots σ 0 σ 1 σ 2 ⋯ is an infinite firing sequence from M 0 M_0 M 0 , so R R R is live by Lemma 3.3, (4)⇒ \Rightarrow ⇒ (1).
Conversely, suppose that I I I does not cover Z \mathbb{Z} Z , and let x x x be an uncovered integer. Let B : = lcm ( b 0 , b 1 , … , b m − 1 ) B:=\operatorname{lcm}(b_0,b_1,\ldots,b_{m-1}) B := lcm ( b 0 , b 1 , … , b m − 1 ) . Every prime factor of B B B divides some b i b_i b i , and hence does not divide W W W , because gcd ( W , b i ) = 1 \gcd(W,b_i)=1 g cd( W , b i ) = 1 ; so gcd ( W , B ) = 1 \gcd(W,B)=1 g cd( W , B ) = 1 . Therefore W W W is invertible modulo B B B : there is an integer W ′ W' W ′ with W W ′ ≡ 1 ( m o d B ) WW'\equiv1\pmod B W W ′ ≡ 1 ( mod B ) . Put z : = ( W ′ x ) m o d B z:=(W'x)\bmod B z := ( W ′ x ) mod B . Then z ∈ N z\in\mathbb{N} z ∈ N (indeed 0 ≤ z < B 0\le z<B 0 ≤ z < B ), and W z ≡ W W ′ x ≡ x ( m o d B ) Wz\equiv WW'x\equiv x\pmod B W z ≡ W W ′ x ≡ x ( mod B ) .
W z ≡ W W ′ x ≡ x ( m o d B ) . Wz\equiv WW'x\equiv x\pmod B. W z ≡ W W ′ x ≡ x ( mod B ) .
By the observation preceding (4) , W z Wz W z is covered iff x x x is; so W z Wz W z is not covered. Hence the set of all z ∈ N z\in\mathbb{N} z ∈ N for which W z Wz W z is not covered is non-empty; let z ∗ z^* z ∗ be its least element. For every z < z ∗ z<z^* z < z ∗ the number W z Wz W z is covered, so (b) gives rounds D 0 → σ 0 D 1 → σ 1 ⋯ → σ z ∗ − 1 D z ∗ D_0\xrightarrow{\sigma_0}D_1\xrightarrow{\sigma_1}\cdots\xrightarrow{\sigma_{z^*-1}}D_{z^*} D 0 σ 0 D 1 σ 1 ⋯ σ z ∗ − 1 D z ∗ , and D z ∗ D_{z^*} D z ∗ is dead by (a). So a dead marking is reachable from M 0 M_0 M 0 , and R R R is not live.
This is where the assumption gcd ( W , b i ) = 1 \gcd(W,b_i)=1 g cd( W , b i ) = 1 is needed: it guarantees that the multiples W z Wz W z , z ∈ N z\in\mathbb{N} z ∈ N , meet every residue class modulo B B B . Without it, (c) can fail. Take I = ( ( 0 , 2 ) ) I=((0,2)) I = (( 0 , 2 )) and W = 4 W=4 W = 4 , and build the ring as in Construction 4.3, ignoring the condition gcd ( W , b 0 ) = 1 \gcd(W,b_0)=1 g cd( W , b 0 ) = 1 . Parts (a) and (b) do not use this condition. Every 4 z 4z 4 z is even and hence covered, so by (b) the counter advances forever, and this marked ring is live by Lemma 3.3, although the odd integers are not covered.
(d) Suppose that R R R is not live. By (c), I I I does not cover Z \mathbb{Z} Z , and the proof of (c) provides z ∗ z^* z ∗ and the firing sequence ρ : = σ 0 σ 1 ⋯ σ z ∗ − 1 \rho:=\sigma_0\sigma_1\cdots\sigma_{z^*-1} ρ := σ 0 σ 1 ⋯ σ z ∗ − 1 from M 0 M_0 M 0 to the dead marking D z ∗ D_{z^*} D z ∗ ; so ρ \rho ρ is a maximal firing sequence. Each β j \beta_j β j occurs in ρ \rho ρ exactly z ∗ z^* z ∗ times, once in each round. By the state equation and (6) , for every j ∈ { 0 , 1 , … , m − 1 } j\in\{0,1,\ldots,m-1\} j ∈ { 0 , 1 , … , m − 1 } ,
D z ∗ ( u j ) = M 0 ( u j ) + W P ( ρ ) ( β j − 1 ) − b j P ( ρ ) ( α j ) = r ˉ j + W z ∗ − b j P ( ρ ) ( α j ) . D_{z^*}(u_j)=M_0(u_j)+W\,\mathcal{P}(\rho)(\beta_{j-1})-b_j\,\mathcal{P}(\rho)(\alpha_j)=\bar r_j+Wz^*-b_j\,\mathcal{P}(\rho)(\alpha_j). D z ∗ ( u j ) = M 0 ( u j ) + W P ( ρ ) ( β j − 1 ) − b j P ( ρ ) ( α j ) = r ˉ j + W z ∗ − b j P ( ρ ) ( α j ) .
As D z ∗ ( u j ) = ( r ˉ j + W z ∗ ) m o d b j D_{z^*}(u_j)=(\bar r_j+Wz^*)\bmod b_j D z ∗ ( u j ) = ( r ˉ j + W z ∗ ) mod b j , this gives P ( ρ ) ( α j ) = ⌊ ( r ˉ j + W z ∗ ) / b j ⌋ = Y z ∗ ( α j ) \mathcal{P}(\rho)(\alpha_j)=\lfloor(\bar r_j+Wz^*)/b_j\rfloor=Y_{z^*}(\alpha_j) P ( ρ ) ( α j ) = ⌊( r ˉ j + W z ∗ ) / b j ⌋ = Y z ∗ ( α j ) . Hence P ( ρ ) = Y z ∗ \mathcal{P}(\rho)=Y_{z^*} P ( ρ ) = Y z ∗ . By Corollary 3.4, every maximal firing sequence from M 0 M_0 M 0 is finite, has the same Parikh vector P ( ρ ) = Y z ∗ \mathcal{P}(\rho)=Y_{z^*} P ( ρ ) = Y z ∗ , and ends in the same dead marking D z ∗ D_{z^*} D z ∗ .
Part (d) says that, whatever the order in which transitions occur, a non-live ring R ( I , W ) R(I,W) R ( I , W ) always stops at the same dead marking after the same numbers of occurrences: each β i \beta_i β i occurs z ∗ z^* z ∗ times and each α i \alpha_i α i occurs ⌊ ( r ˉ i + W z ∗ ) / b i ⌋ \lfloor(\bar r_i+Wz^*)/b_i\rfloor ⌊( r ˉ i + W z ∗ ) / b i ⌋ times. So the rounds of (b) are only one way of running the ring; other orders of firing, in which some β i \beta_i β i may occur twice before another β j \beta_j β j occurs at all, end in the same dead marking (see Example 4.5).
Example 4.5 (a live and a non-live instance). Let W = 5 W=5 W = 5 and consider the covering instances
I + = ( ( 0 , 2 ) , ( 1 , 4 ) , ( 3 , 4 ) ) and I − = ( ( 0 , 2 ) , ( 1 , 4 ) , ( 2 , 4 ) ) , I_+=((0,2),(1,4),(3,4)) \qquad\text{and} \qquad I_-=((0,2),(1,4),(2,4)), I + = (( 0 , 2 ) , ( 1 , 4 ) , ( 3 , 4 )) and I − = (( 0 , 2 ) , ( 1 , 4 ) , ( 2 , 4 )) ,
which differ only in the third pair. As noted after Definition 4.1, I + I_+ I + covers Z \mathbb{Z} Z . The instance I − I_- I − does not: the class 2 mod 4 contains only even integers, which are covered by 0 mod 2 anyway, so the integers x x x with x x x mod 4 = 3 remain uncovered. Since W = 5 W=5 W = 5 is a prime larger than all moduli, Construction 4.3 applies, and B = lcm ( 2 , 4 , 4 ) = 4 B=\operatorname{lcm}(2,4,4)=4 B = lcm ( 2 , 4 , 4 ) = 4 . We list markings in the order u 0 , v 0 , u 1 , v 1 , u 2 , v 2 u_0,v_0,u_1,v_1,u_2,v_2 u 0 , v 0 , u 1 , v 1 , u 2 , v 2 . We have r ˉ 0 = ( − 0 ) mod 2 = 0 \bar r_0=(-0)\mathbin{\operatorname{mod}}2=0 r ˉ 0 = ( − 0 ) mod 2 = 0 and r ˉ 1 = ( − 1 ) mod 4 = 3 \bar r_1=(-1)\mathbin{\operatorname{mod}}4=3 r ˉ 1 = ( − 1 ) mod 4 = 3 in both cases, while r ˉ 2 = ( − 3 ) mod 4 = 1 \bar r_2=(-3)\mathbin{\operatorname{mod}}4=1 r ˉ 2 = ( − 3 ) mod 4 = 1 for I + I_+ I + and r ˉ 2 = ( − 2 ) mod 4 = 2 \bar r_2=(-2)\mathbin{\operatorname{mod}}4=2 r ˉ 2 = ( − 2 ) mod 4 = 2 for I − I_- I − . So the initial markings are
M 0 + = ( 0 , 5 , 3 , 2 , 1 , 4 ) and M 0 − = ( 0 , 5 , 3 , 2 , 2 , 3 ) . M_0^+=(0,5,3,2,1,4) \qquad\text{and} \qquad M_0^-=(0,5,3,2,2,3). M 0 + = ( 0 , 5 , 3 , 2 , 1 , 4 ) and M 0 − = ( 0 , 5 , 3 , 2 , 2 , 3 ) .
Figure 3 shows both rings; they have the same weights and differ only in the initial marking of u 2 u_2 u 2 and v 2 v_2 v 2 .
Figure 3. The two rings of Example 4.5, drawn as in Figure 2 , with ( b 0 , b 1 , b 2 ) = ( 2 , 4 , 4 ) (b_0,b_1,b_2)=(2,4,4) ( b 0 , b 1 , b 2 ) = ( 2 , 4 , 4 ) and W = 5 W=5 W = 5 ; numbers inside places give the initial markings. The rings differ only in the initial marking of u 2 u_2 u 2 and v 2 v_2 v 2 . Ring (a) is live. Ring (b) is not live: every maximal firing sequence ends in the dead marking D 3 D_3 D 3 , which has 1, 4, 2, 3, 1, 4 tokens on u 0 , v 0 , u 1 , v 1 , u 2 , v 2 u_0,v_0,u_1,v_1,u_2,v_2 u 0 , v 0 , u 1 , v 1 , u 2 , v 2 .
By Lemma 4.4 , everything depends on which of the numbers W z = 5 z Wz=5z W z = 5 z , z ∈ N z\in\mathbb{N} z ∈ N , are covered. Since 5 ≡ 1 ( m o d 4 ) 5\equiv1\pmod{4} 5 ≡ 1 ( mod 4 ) , we have 5 z ≡ z ( m o d 4 ) 5z\equiv z\pmod{4} 5 z ≡ z ( mod 4 ) , and since B = 4 B=4 B = 4 , it suffices to consider z = 0 , 1 , 2 , 3 z=0,1,2,3 z = 0 , 1 , 2 , 3 :
Table 3.
In the terms of the paragraph “How the ring works”, the counter of R ( I + , 5 ) R(I_{+},5) R ( I + , 5 ) can advance forever, whereas the counter of R ( I − , 5 ) R(I_{-},5) R ( I − , 5 ) advances from 0 to 1, 2 and 3 and gets stuck at 3, because 15 is not covered by I − I_{-} I − .
The live ring R ( I + , 5 ) R(I_{+},5) R ( I + , 5 ) . Every 5 z 5z 5 z is covered, so R ( I + , 5 ) R(I_{+},5) R ( I + , 5 ) is live by Lemma 4.4 (c): its counter advances forever. Liveness can also be seen directly. The least common multiple of all weights is L = lcm ( 2 , 5 , 4 , 5 , 4 , 5 ) = 20 L=\operatorname{lcm}(2,5,4,5,4,5)=20 L = lcm ( 2 , 5 , 4 , 5 , 4 , 5 ) = 20 , so by Lemma 2.3 the minimal T T T -invariant is given by x T ( α 0 ) = 10 x_T(\alpha_0)=10 x T ( α 0 ) = 10 , x T ( α 1 ) = x T ( α 2 ) = 5 x_T(\alpha_1)=x_T(\alpha_2)=5 x T ( α 1 ) = x T ( α 2 ) = 5 and x T ( β i ) = 4 x_T(\beta_i)=4 x T ( β i ) = 4 . The sequence
β 0 α 1 2 β 1 2 α 2 2 β 2 α 0 2 β 2 α 0 3 β 0 2 α 1 2 β 1 α 2 2 β 2 α 0 2 β 2 α 0 3 β 0 α 1 β 1 α 2 , \beta_0\alpha_1^2\beta_1^2\alpha_2^2\beta_2\alpha_0^2\beta_2\alpha_0^3\beta_0^2\alpha_1^2\beta_1\alpha_2^2\beta_2\alpha_0^2\beta_2\alpha_0^3\beta_0\alpha_1\beta_1\alpha_2, β 0 α 1 2 β 1 2 α 2 2 β 2 α 0 2 β 2 α 0 3 β 0 2 α 1 2 β 1 α 2 2 β 2 α 0 2 β 2 α 0 3 β 0 α 1 β 1 α 2 ,
where α 2 \alpha^2 α 2 stands for α α \alpha\alpha α α and so on, is a firing sequence from M 0 + M_0^{+} M 0 + with Parikh vector x T x_T x T ; it begins with
M 0 + → β 0 ( 0 , 0 , 8 , 2 , 1 , 4 ) → α 1 ( 0 , 0 , 4 , 6 , 1 , 4 ) → α 1 ( 0 , 0 , 0 , 10 , 1 , 4 ) . M_0^{+}\xrightarrow{\beta_0}(0,0,8,2,1,4)\xrightarrow{\alpha_1}(0,0,4,6,1,4)\xrightarrow{\alpha_1}(0,0,0,10,1,4). M 0 + β 0 ( 0 , 0 , 8 , 2 , 1 , 4 ) α 1 ( 0 , 0 , 4 , 6 , 1 , 4 ) α 1 ( 0 , 0 , 0 , 10 , 1 , 4 ) .
By the state equation, it leads back to M 0 + M_0^{+} M 0 + , so repeating it forever gives an infinite firing sequence, and R ( I + , 5 ) R(I_{+},5) R ( I + , 5 ) is live by Lemma 3.3 , (4)⇒ \Rightarrow ⇒ (1). (The reachability graph of R ( I + , 5 ) R(I_{+},5) R ( I + , 5 ) , computed by machine, has 74 markings, none of which is dead.)
The non-live ring R ( I − , 5 ) R(I_{-},5) R ( I − , 5 ) . The least z ∈ N z\in\mathbb{N} z ∈ N for which 5 z 5z 5 z is not covered by I − I_{-} I − is z ∗ = 3 z^{*}=3 z ∗ = 3 . By Lemma 4.4 (d), every maximal firing sequence from M 0 − M_0^{-} M 0 − is finite; in it, each β i \beta_i β i occurs exactly 3 times, and α 0 \alpha_0 α 0 , α 1 \alpha_1 α 1 , α 2 \alpha_2 α 2 occur ⌊ 15 / 2 ⌋ = 7 \lfloor15/2\rfloor=7 ⌊ 15/2 ⌋ = 7 , ⌊ ( 3 + 15 ) / 4 ⌋ = 4 \lfloor(3+15)/4\rfloor=4 ⌊( 3 + 15 ) /4 ⌋ = 4 and ⌊ ( 2 + 15 ) / 4 ⌋ = 4 \lfloor(2+15)/4\rfloor=4 ⌊( 2 + 15 ) /4 ⌋ = 4 times; and it ends in the dead marking D 3 D_3 D 3 with D 3 ( u i ) = ( r ˉ i + 15 ) m o d b i D_3(u_i)=(\bar r_i+15)\bmod b_i D 3 ( u i ) = ( r ˉ i + 15 ) mod b i and D 3 ( v i ) = 5 − D 3 ( u i ) D_3(v_i)=5-D_3(u_i) D 3 ( v i ) = 5 − D 3 ( u i ) , i.e.
D 3 = ( 1 , 4 , 2 , 3 , 1 , 4 ) . D_3=(1,4,2,3,1,4). D 3 = ( 1 , 4 , 2 , 3 , 1 , 4 ) .
The rounds of Lemma 4.4 (b) reach D 3 D_3 D 3 as follows. At D 0 = M 0 − D_0=M_0^{-} D 0 = M 0 − , the number 5 ⋅ 0 = 0 5\cdot0=0 5 ⋅ 0 = 0 lies in the class 0 mod 2 of the first pair, so the first round starts with β 0 \beta_0 β 0 :
D 0 = ( 0 , 5 , 3 , 2 , 2 , 3 ) → β 0 ( 0 , 0 , 8 , 2 , 2 , 3 ) → α 1 2 ( 0 , 0 , 0 , 10 , 2 , 3 ) → β 1 ( 0 , 0 , 0 , 5 , 7 , 3 ) D_0=(0,5,3,2,2,3)\xrightarrow{\beta_0}(0,0,8,2,2,3)\xrightarrow{\alpha_1^2}(0,0,0,10,2,3)\xrightarrow{\beta_1}(0,0,0,5,7,3) D 0 = ( 0 , 5 , 3 , 2 , 2 , 3 ) β 0 ( 0 , 0 , 8 , 2 , 2 , 3 ) α 1 2 ( 0 , 0 , 0 , 10 , 2 , 3 ) β 1 ( 0 , 0 , 0 , 5 , 7 , 3 )
→ α 2 ( 0 , 0 , 0 , 5 , 3 , 7 ) → β 2 ( 5 , 0 , 0 , 5 , 3 , 2 ) → α 0 2 ( 1 , 4 , 0 , 5 , 3 , 2 ) = D 1 . \xrightarrow{\alpha_2}(0,0,0,5,3,7)\xrightarrow{\beta_2}(5,0,0,5,3,2)\xrightarrow{\alpha_0^2}(1,4,0,5,3,2)=D_1. α 2 ( 0 , 0 , 0 , 5 , 3 , 7 ) β 2 ( 5 , 0 , 0 , 5 , 3 , 2 ) α 0 2 ( 1 , 4 , 0 , 5 , 3 , 2 ) = D 1 .
Next, 5 ⋅ 1 = 5 5\cdot1=5 5 ⋅ 1 = 5 lies in the class 1 mod 4 of the second pair, and 5 ⋅ 2 = 10 5\cdot2=10 5 ⋅ 2 = 10 in the class 0 mod 2 of the first pair (and also in 2 mod 4); so the next two rounds can be
D 1 → β 1 α 2 2 β 0 α 1 α 0 3 D 2 = ( 0 , 5 , 1 , 4 , 0 , 5 ) → β 0 α 1 β 1 α 2 β 2 α 0 2 D 3 . D_1\xrightarrow{\beta_1\alpha_2^2\beta_0\alpha_1\alpha_0^3}D_2=(0,5,1,4,0,5)\xrightarrow{\beta_0\alpha_1\beta_1\alpha_2\beta_2\alpha_0^2}D_3. D 1 β 1 α 2 2 β 0 α 1 α 0 3 D 2 = ( 0 , 5 , 1 , 4 , 0 , 5 ) β 0 α 1 β 1 α 2 β 2 α 0 2 D 3 .
At D 3 D_3 D 3 , each place u i u_i u i holds a non-zero remainder (1, 2 and 1 tokens, fewer than b i = 2 , 4 , 4 b_i=2,4,4 b i = 2 , 4 , 4 ), so each v i v_i v i holds fewer than W = 5 W=5 W = 5 tokens, and no transition is enabled, in accordance with Lemma 4.4 (a). Other orders of firing lead to the same Parikh vector and the same dead marking, by Lemma 4.4 (d). For instance, firing in every step the first enabled transition in the order α 0 , β 0 , α 1 , β 1 , α 2 , β 2 \alpha_0,\beta_0,\alpha_1,\beta_1,\alpha_2,\beta_2 α 0 , β 0 , α 1 , β 1 , α 2 , β 2 yields the maximal firing sequence
β 0 α 1 2 β 2 2 α 0 3 β 2 α 0 3 β 0 2 α 1 β 1 α 2 β 2 α 0 2 \beta_0\alpha_1^2\beta_2^2\alpha_0^3\beta_2\alpha_0^3\beta_0^2\alpha_1\beta_1\alpha_2\beta_2\alpha_0^2 β 0 α 1 2 β 2 2 α 0 3 β 2 α 0 3 β 0 2 α 1 β 1 α 2 β 2 α 0 2
of length 24, which also ends in D 3 D_3 D 3 ; in it, β 1 \beta_1 β 1 occurs twice before β 2 \beta_2 β 2 occurs at all. (The reachability graph of R ( I − , 5 ) R(I_{-},5) R ( I − , 5 ) has 93 markings, and D 3 D_3 D 3 is the only dead one.)
In the live ring R ( I + , 5 ) R(I_{+},5) R ( I + , 5 ) , the marking D 3 = ( 1 , 4 , 2 , 3 , 0 , 5 ) D_3=(1,4,2,3,0,5) D 3 = ( 1 , 4 , 2 , 3 , 0 , 5 ) is not dead: there, D 3 ( u 2 ) = ( 1 + 15 ) m o d 4 = 0 D_3(u_2)=(1+15)\bmod4=0 D 3 ( u 2 ) = ( 1 + 15 ) mod 4 = 0 , so v 2 v_2 v 2 holds all 5 tokens of its pair and β 2 \beta_2 β 2 is enabled, as 15 is covered by the class 3 mod 4 of I + I_{+} I + .
Theorem 4.6 (main result). RINGLIVE is coNP-complete. It is coNP-hard already for instances ( N , M 0 ) (N,M_0) ( N , M 0 ) in which N N N is token-conserving and all arc weights and all token numbers M 0 ( s ) M_0(s) M 0 ( s ) are bounded by O ( n 3 / 2 log 3 n ) O(n^{3/2}\log^3 n) O ( n 3/2 log 3 n ) , where n n n is the number of places; in particular, RINGLIVE is coNP-hard in the strong sense.
Proof. Membership is Proposition 3.5 . For hardness, we reduce 3-SAT, restricted to formulas that have at least one clause and no repeated clauses and whose clauses consist of three literals over three distinct variables (which is still NP-complete, see the proof of Proposition 4.2 ), to the complement of RingLive. Given such a formula φ \varphi φ with k k k variables, compute I ( φ ) I(\varphi) I ( φ ) as in Proposition 4.2 , let W W W be the least prime larger than all moduli of I ( φ ) I(\varphi) I ( φ ) , and output the marked ring R ( I ( φ ) , W ) R(I(\varphi), W) R ( I ( φ ) , W ) .
Correctness. Since W W W is a prime larger than every modulus b i b_i b i of I ( φ ) I(\varphi) I ( φ ) , we have gcd ( W , b i ) = 1 \operatorname{gcd}(W,b_i)=1 gcd ( W , b i ) = 1 , so Construction 4.3 applies. By Proposition 4.2 and Lemma 4.4 (c),
φ is unsatisfiable ⟺ I ( φ ) covers Z ⟺ R ( I ( φ ) , W ) is live . \varphi\text{ is unsatisfiable}\quad\Longleftrightarrow\quad I(\varphi)\text{ covers }\mathbb{Z}\quad\Longleftrightarrow\quad R(I(\varphi),W)\text{ is live}. φ is unsatisfiable ⟺ I ( φ ) covers Z ⟺ R ( I ( φ ) , W ) is live .
Size and running time. All moduli of I ( φ ) I(\varphi) I ( φ ) are at most p k 3 p_k^3 p k 3 , so by the Bertrand–Chebyshev theorem (for every integer h ≥ 1 h\ge1 h ≥ 1 there is a prime p p p with h < p ≤ 2 h h<p\le2h h < p ≤ 2 h ) we have W ≤ 2 p k 3 W\le2p_k^3 W ≤ 2 p k 3 ; and W W W can be found by trial division in time polynomial in p k p_k p k , hence in k k k . The ring has n = 2 m n=2m n = 2 m places, where m = l + ∑ j = 1 k ( p j − 2 ) m=l+\sum_{j=1}^{k}(p_j-2) m = l + ∑ j = 1 k ( p j − 2 ) by Proposition 4.2 . Since the j j j -th odd prime is at least 2 j + 1 2j+1 2 j + 1 , we have m ≥ ∑ j = 1 k ( p j − 2 ) ≥ ∑ j = 1 k ( 2 j − 1 ) = k 2 m\ge\sum_{j=1}^{k}(p_j-2)\ge\sum_{j=1}^{k}(2j-1)=k^2 m ≥ ∑ j = 1 k ( p j − 2 ) ≥ ∑ j = 1 k ( 2 j − 1 ) = k 2 , so n ≥ 2 k 2 n\ge2k^2 n ≥ 2 k 2 , i.e. k ≤ n / 2 k\le\sqrt{n/2} k ≤ n /2 . Every arc weight is some b i b_i b i or W W W , hence at most W W W , and every place initially carries at most W W W tokens (M 0 ( u i ) = r ˉ i < b i M_0(u_i)=\bar r_i<b_i M 0 ( u i ) = r ˉ i < b i and M 0 ( v i ) = W − r ˉ i ≤ W M_0(v_i)=W-\bar r_i\le W M 0 ( v i ) = W − r ˉ i ≤ W ). Since p k = O ( k log k ) p_k=O(k\log k) p k = O ( k log k ) , all these numbers are bounded by
W ≤ 2 p k 3 = O ( k 3 log 3 k ) = O ( n 3 / 2 log 3 n ) . W\le2p_k^3=O(k^3\log^3 k)=O(n^{3/2}\log^3 n). W ≤ 2 p k 3 = O ( k 3 log 3 k ) = O ( n 3/2 log 3 n ) .
So RingLive is coNP-hard already for instances whose numbers are bounded by a polynomial in the number of places, which is coNP-hardness in the strong sense.
Lemma 4.8 (circuits; [18 Prop. 6.3] ). A marked weighted T T T -system ( N , M 0 ) (N,M_0) ( N , M 0 ) is live iff for every elementary circuit γ \gamma γ of N N N , the marked ring ( N γ , M 0 ∣ γ ) (N_\gamma,M_{0|\gamma}) ( N γ , M 0∣ γ ) is live.
Idea. The places of a circuit are changed only by the transitions of the circuit, so every behaviour of N N N restricts to a behaviour of each ring N γ N_\gamma N γ . Conversely, if a transition can no longer occur, then one of its input places never gets enough tokens again, so the input transition of this place also stops occurring, and so on backwards, until a circuit closes.
Proof. We use two facts. (i) Firing a transition t t t removes tokens only from places whose (only) output transition is t t t ; hence an enabled transition stays enabled until it fires. (ii) The input and output transitions of the places of an elementary circuit γ \gamma γ belong to γ \gamma γ . So, for every firing sequence σ \sigma σ from M 0 M_0 M 0 , the subsequence σ ∣ γ \sigma|_\gamma σ ∣ γ of the occurrences of transitions of γ \gamma γ is a firing sequence of N γ N_\gamma N γ from M 0 ∣ γ M_{0|\gamma} M 0∣ γ , which leads to the restriction to γ \gamma γ of the marking reached by σ \sigma σ .
Suppose that ( N , M 0 ) (N,M_0) ( N , M 0 ) is live. Firing the transitions in turn, which is possible by liveness, gives an infinite firing sequence from M 0 M_0 M 0 in which every transition occurs infinitely often. By (ii), its restriction to an elementary circuit γ \gamma γ is an infinite firing sequence of N γ N_\gamma N γ from M 0 ∣ γ M_{0|\gamma} M 0∣ γ , so ( N γ , M 0 ∣ γ ) (N_\gamma,M_{0|\gamma}) ( N γ , M 0∣ γ ) is live by Lemma 3.3 , ( 4 ) ⇒ ( 1 ) (4)\Rightarrow(1) ( 4 ) ⇒ ( 1 ) .
Conversely, suppose that ( N , M 0 ) (N,M_0) ( N , M 0 ) is not live: some transition t t t occurs in no firing sequence from some reachable marking M M M . Let ρ \rho ρ be a maximal firing sequence from M M M that is fair , i.e. every transition that is enabled at some point of ρ \rho ρ occurs at a later point of ρ \rho ρ . Such a ρ \rho ρ exists by (i): keep the enabled transitions in a queue; repeatedly fire the first one, remove it from the queue, and append every enabled transition that is not yet in the queue. Let τ \tau τ be a transition that occurs only finitely often in ρ \rho ρ , for instance t t t . After its last occurrence, τ \tau τ is never enabled again, by fairness. Only τ \tau τ removes tokens from its input places, so their token numbers do not decrease after this point. Hence some input place q q q of τ \tau τ carries fewer than F ( q , τ ) F(q,\tau) F ( q , τ ) tokens from some point of ρ \rho ρ on (otherwise, from some point on, all input places of τ \tau τ would carry enough tokens, and τ \tau τ would be enabled). Each occurrence of the input transition of q q q adds tokens to q q q , so this transition, too, occurs only finitely often in ρ \rho ρ . Starting with τ 0 : = t \tau_0:=t τ 0 := t and repeating this step, we obtain transitions τ 0 , τ 1 , τ 2 , … \tau_0,\tau_1,\tau_2,\ldots τ 0 , τ 1 , τ 2 , … that occur only finitely often in ρ \rho ρ , and places q 0 , q 1 , q 2 , … q_0,q_1,q_2,\ldots q 0 , q 1 , q 2 , … such that q i q_i q i has the output transition τ i \tau_i τ i and the input transition τ i + 1 \tau_{i+1} τ i + 1 and carries fewer than F ( q i , τ i ) F(q_i,\tau_i) F ( q i , τ i ) tokens from some point of ρ \rho ρ on. Since T T T is finite, there is a least b b b such that τ b = τ a \tau_b=\tau_a τ b = τ a for some a < b a<b a < b . Then τ a , τ a + 1 , … , τ b − 1 \tau_a,\tau_{a+1},\ldots,\tau_{b-1} τ a , τ a + 1 , … , τ b − 1 are distinct, and so are q a , q a + 1 , … , q b − 1 q_a,q_{a+1},\ldots,q_{b-1} q a , q a + 1 , … , q b − 1 , whose output transitions differ; hence γ = q b − 1 τ b − 1 q b − 2 τ b − 2 ⋯ q a τ a \gamma=q_{b-1}\tau_{b-1}q_{b-2}\tau_{b-2}\cdots q_a\tau_a γ = q b − 1 τ b − 1 q b − 2 τ b − 2 ⋯ q a τ a is an elementary circuit of N N N . From some point of ρ \rho ρ on, every place of γ \gamma γ carries fewer tokens than its output transition needs. By (ii), the marking reached at this point, which is reachable from M 0 M_0 M 0 , restricts to a dead marking of N γ N_\gamma N γ that is reachable from M 0 ∣ γ M_{0|\gamma} M 0∣ γ . So ( N γ , M 0 ∣ γ ) (N_\gamma,M_{0|\gamma}) ( N γ , M 0∣ γ ) is not live. □ \square □
Corollary 4.9 (weighted T T T -systems). Liveness of weighted T T T -systems is coNP-complete; it is coNP-hard in the strong sense already for token-conserving rings.
Proof. A marked weighted T T T -system is given by its places, transitions, arc weights and initial marking, with numbers in binary. Hardness holds by Theorem 4.6 , since ring nets are weighted T T T -systems. For membership, let ( N , M 0 ) (N,M_0) ( N , M 0 ) be a marked weighted T T T -system that is not live. By Lemma 4.8 , some elementary circuit γ \gamma γ of N N N induces a marked ring ( N γ , M 0 ∣ γ ) (N_\gamma,M_{0|\gamma}) ( N γ , M 0∣ γ ) that is not live. All numbers of this ring occur in ( N , M 0 ) (N,M_0) ( N , M 0 ) , so, by the proof of Proposition 3.5 , there is a vector Y Y Y whose entries have polynomially many bits such that M 0 ∣ γ + C γ ⋅ Y M_{0|\gamma}+C_\gamma\cdot Y M 0∣ γ + C γ ⋅ Y is a dead marking of N γ N_\gamma N γ , where C γ C_\gamma C γ is the incidence matrix of N γ N_\gamma N γ . The pair ( γ , Y ) (\gamma,Y) ( γ , Y ) is a certificate of polynomial size for non-liveness: one can check in polynomial time that γ \gamma γ is an elementary circuit and that M 0 ∣ γ + C γ ⋅ Y M_{0|\gamma}+C_\gamma\cdot Y M 0∣ γ + C γ ⋅ Y is a dead marking of N γ N_\gamma N γ , and then ( N γ , M 0 ∣ γ ) (N_\gamma,M_{0|\gamma}) ( N γ , M 0∣ γ ) is not live by Lemma 3.3 , ( 1 ) ⇒ ( 6 ) (1)\Rightarrow(6) ( 1 ) ⇒ ( 6 ) , and ( N , M 0 ) (N,M_0) ( N , M 0 ) is not live by Lemma 4.8 . □ \square □
Chip-firing on simple digraphs
Chip-firing is a solitaire game on a graph, introduced for undirected graphs by Björner, Lovász and Shor [3 ] and studied on directed graphs by Björner and Lovász [2 ] . In this section we show that its halting problem is NP-complete on simple directed graphs, and NP-hard already on strongly connected ones, by a reduction from non-liveness of token-conserving rings. We first recall the definitions.
Chip-firing. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a finite directed graph (digraph ) with vertex set V V V and edge set E ⊆ V × V E \subseteq V \times V E ⊆ V × V . Such a digraph is simple : since E E E is a set, every edge occurs at most once; we also exclude loops ( v , v ) (v,v) ( v , v ) . (Farrell and Levine [14 ] also consider multigraphs , in which an edge may occur several times.) The out-degree d ( v ) d(v) d ( v ) of a vertex v v v is the number of edges ( v , w ) ∈ E (v,w) \in E ( v , w ) ∈ E ; the vertices w w w with ( v , w ) ∈ E (v,w) \in E ( v , w ) ∈ E are the out-neighbours of v v v , and the vertices y y y with ( y , v ) ∈ E (y,v) \in E ( y , v ) ∈ E are its in-neighbours . A chip configuration is a vector σ ∈ N V \sigma\in\mathbb{N}^{V} σ ∈ N V ; we think of σ ( v ) \sigma(v) σ ( v ) as the number of chips on v v v . A vertex v v v is active at σ \sigma σ if d ( v ) ≥ 1 d(v) \ge1 d ( v ) ≥ 1 and σ ( v ) ≥ d ( v ) \sigma(v) \ge d(v) σ ( v ) ≥ d ( v ) ; thus a vertex without outgoing edges never fires (in a strongly connected digraph with at least two vertices, the setting of [14 ] , there are no such vertices). An active vertex v v v may fire : it sends one chip along each of its outgoing edges, i.e. it loses d ( v ) d(v) d ( v ) chips, and each of its out-neighbours gains one chip. A legal game from σ \sigma σ is a finite or infinite sequence of firings, each of which fires a vertex that is active at the current configuration. A configuration is stable if no vertex is active at it, and σ \sigma σ halts if some legal game from σ \sigma σ ends in a stable configuration. The Hᴇᴀʟᴛɪɴɢ Pʀᴏʙʟᴇᴍ ғᴏʀ Cʜɪᴘ-Fɪʀɪɴɢ asks, given G G G and σ \sigma σ (with numbers in binary), whether σ \sigma σ halts.
In Petri net terms, chip-firing on G G G is the net whose places are the vertices of G G G and which has a transition f v f_v f v for every vertex v v v with d ( v ) ≥ 1 d(v) \ge1 d ( v ) ≥ 1 ; the transition f v f_v f v takes d ( v ) d(v) d ( v ) tokens from v v v and puts one token on each out-neighbour of v v v . Chip configurations are markings, legal games are firing sequences, stable configurations are dead markings, and σ \sigma σ halts iff a dead marking is reachable from σ \sigma σ .
What was known. Björner and Lovász [2 ] showed that if some legal game from σ \sigma σ ends in a stable configuration, then no legal game from σ \sigma σ is infinite, and all legal games from σ \sigma σ that cannot be continued end in the same stable configuration, after the same number of firings of each vertex. (For rings, Corollary 3.4 is the analogous statement.) So it does not matter which active vertex is fired: if σ \sigma σ halts, every legal game from σ \sigma σ stops after finitely many firings. Farrell and Levine [14 Cor. 3.2] proved that the halting problem is NP-complete for strongly connected directed multigraphs; their hard instances may have large edge multiplicities. They asked “whether the Hᴀʟᴛɪɴɢ Pʀᴏʙʟᴇᴍ ғᴏʀ Cʜɪᴘ-Fɪʀɪɴɢ remains NP-hard when restricted to simple directed graphs” [14 Sect. 3.1] . The question is also posed as an open problem in the Eᴠʀᴇs open problem collection [12 ] , whose overview page on chip-firing [11 ] conjectures that the problem is NP-hard and records that it is polynomial for simple Eulerian digraphs. See also [3 , 27 ] .
The reduction. The idea is to let each place s i s_i s i of a token-conserving ring become a vertex v i v_i v i , and to replace the transition t i t_i t i , which moves A i A_i A i tokens from s i s_i s i to s i + 1 s_{i+1} s i + 1 , by A i A_i A i parallel paths of length two from v i v_i v i to v i + 1 v_{i+1} v i + 1 .
Construction 5.1 (the digraph G N G_N G N ). Let N N N be a token-conserving ring with weights A i : = a i − b i A_i := a_i - b_i A i := a i − b i (0 ≤ i ≤ n − 1 0 \le i \le n-1 0 ≤ i ≤ n − 1 ), and let M 0 M_0 M 0 be a marking of N N N . The digraph G N G_N G N has the vertices
v 0 , v 1 , … , v n − 1 and w i , k ( 0 ≤ i ≤ n − 1 , 1 ≤ k ≤ A i ) , v_0,v_1,\ldots,v_{n-1}\qquad\text{and}\qquad w_{i,k}\quad(0 \le i \le n-1,\ 1 \le k \le A_i), v 0 , v 1 , … , v n − 1 and w i , k ( 0 ≤ i ≤ n − 1 , 1 ≤ k ≤ A i ) ,
and the edges v i → w i , k v_i \to w_{i,k} v i → w i , k and w i , k → v i + 1 w_{i,k} \to v_{i+1} w i , k → v i + 1 for all i i i and k k k , where v n : = v 0 v_n := v_0 v n := v 0 . The chip configuration σ M 0 \sigma_{M_0} σ M 0 puts M 0 ( s i ) M_0(s_i) M 0 ( s i ) chips on v i v_i v i , for every i i i , and no chips on the vertices w i , k w_{i,k} w i , k . The vertex v i v_i v i plays the role of the place s i s_i s i , and the A i A_i A i paths v i → w i , k → v i + 1 v_i \to w_{i,k} \to v_{i+1} v i → w i , k → v i + 1 play the role of the transition t i t_i t i : firing v i v_i v i sends A i A_i A i chips into these paths, one into each, and firing the vertices w i , k w_{i,k} w i , k delivers them to v i + 1 v_{i+1} v i + 1 . The digraph G N G_N G N is simple: it has no loops, and no edge occurs twice, because the vertices w i , k w_{i,k} w i , k are distinct. It is strongly connected, since the paths lead all around the ring. It has n + ∑ i A i n+\sum_i A_i n + ∑ i A i vertices and 2 ∑ i A i 2\sum_i A_i 2 ∑ i A i edges, and the out-degrees are d ( v i ) = A i d(v_i)=A_i d ( v i ) = A i and d ( w i , k ) = 1 d(w_{i,k})=1 d ( w i , k ) = 1 . Figure 4 shows an example.
Figure 4. The digraph G N G_N G N of Construction 5.1 for the token-conserving ring with n = 2 n=2 n = 2 and weights A 0 = 2 A_0=2 A 0 = 2 , A 1 = 3 A_1=3 A 1 = 3 (Example 5.3). The numbers inside v 0 v_0 v 0 and v 1 v_1 v 1 are their chips in σ M 0 \sigma_{M_0} σ M 0 for M 0 = ( 3 , 0 ) M_0=(3,0) M 0 = ( 3 , 0 ) ; the vertices w i , k w_{i,k} w i , k carry no chips. Firing v 0 v_0 v 0 and then w 0 , 1 w_{0,1} w 0 , 1 and w 0 , 2 w_{0,2} w 0 , 2 has the same effect as one occurrence of t 0 t_0 t 0 .
Proposition 5.2. Let N N N be a token-conserving ring and M 0 M_0 M 0 a marking of N N N . Then σ M 0 \sigma_{M_0} σ M 0 halts on G N G_N G N iff M 0 M_0 M 0 is not live.
Proof. Let A i A_i A i be the weights of N N N . By (2) , ( C ⋅ Y ) ( s i ) = A i − 1 Y i − 1 − A i Y i (C\cdot Y)(s_i)=A_{i-1}Y_{i-1}-A_iY_i ( C ⋅ Y ) ( s i ) = A i − 1 Y i − 1 − A i Y i for every Y ∈ Z n Y\in\mathbb{Z}^n Y ∈ Z n .
If M 0 M_0 M 0 is not live, then σ M 0 \sigma_{M_0} σ M 0 halts. By Lemma 3.3, some firing sequence ρ \rho ρ leads from M 0 M_0 M 0 to a dead marking D D D . We translate ρ \rho ρ into a legal game: every occurrence of a transition t i t_i t i in ρ \rho ρ is replaced by a block of firings, namely a firing of v i v_i v i , followed by one firing of each of the vertices w i , 1 , w i , 2 , … , w i , A i w_{i,1},w_{i,2},\ldots,w_{i,A_i} w i , 1 , w i , 2 , … , w i , A i . We claim that before and after each block, every vertex v j v_j v j carries as many chips as s j s_j s j carries tokens at the current marking of N N N , and the vertices w j , k w_{j,k} w j , k carry no chips. This holds at the start, by the definition of σ M 0 \sigma_{M_0} σ M 0 . Suppose that it holds before the block for an occurrence of t i t_i t i at a marking M M M . Since t i t_i t i is enabled at M M M , the vertex v i v_i v i carries M ( s i ) ≥ A i = d ( v i ) M(s_i)\ge A_i=d(v_i) M ( s i ) ≥ A i = d ( v i ) chips, so it is active. Firing it leaves M ( s i ) − A i M(s_i)-A_i M ( s i ) − A i chips on v i v_i v i and puts one chip on each w i , k w_{i,k} w i , k . Then each w i , k w_{i,k} w i , k is active, as d ( w i , k ) = 1 d(w_{i,k})=1 d ( w i , k ) = 1 , and firing it moves its chip to v i + 1 v_{i+1} v i + 1 . After the block, v i v_i v i has lost A i A_i A i chips, v i + 1 v_{i+1} v i + 1 has gained A i A_i A i chips, and the vertices w i , k w_{i,k} w i , k are empty again; this is exactly the effect of t i t_i t i on the marking. (For n = 1 n=1 n = 1 , v i + 1 = v i v_{i+1}=v_i v i + 1 = v i , and v 0 v_0 v 0 loses and regains A 0 A_0 A 0 chips, just as s 0 s_0 s 0 loses and regains A 0 A_0 A 0 tokens.) So at the end of the game the configuration is D D D on the vertices v j v_j v j and 0 0 0 on the vertices w j , k w_{j,k} w j , k . It is stable: v j v_j v j carries D ( s j ) < A j = d ( v j ) D(s_j)<A_j=d(v_j) D ( s j ) < A j = d ( v j ) chips, because D D D is dead, and w j , k w_{j,k} w j , k carries 0 < 1 = d ( w j , k ) 0<1=d(w_{j,k}) 0 < 1 = d ( w j , k ) chips. Hence σ M 0 \sigma_{M_0} σ M 0 halts.
If σ M 0 \sigma_{M_0} σ M 0 halts, then M 0 M_0 M 0 is not live. Let a legal game from σ M 0 \sigma_{M_0} σ M 0 end in a stable configuration τ \tau τ , and for every vertex x x x let u ( x ) u(x) u ( x ) be the number of firings of x x x in this game. Each firing of x x x removes d ( x ) d(x) d ( x ) chips from x x x , and each firing of an in-neighbour of x x x adds one chip to x x x ; so, by counting,
τ ( x ) = σ M 0 ( x ) − d ( x ) u ( x ) + ∑ y : ( y , x ) ∈ E u ( y ) for every vertex x . \tau(x)=\sigma_{M_0}(x)-d(x)u(x)+\sum_{y:(y,x)\in E}u(y)\qquad\text{for every vertex }x. τ ( x ) = σ M 0 ( x ) − d ( x ) u ( x ) + y : ( y , x ) ∈ E ∑ u ( y ) for every vertex x .
(This is the state equation (1) of the Petri net described above.) The only in-neighbour of w i , k w_{i,k} w i , k is v i v_i v i , so τ ( w i , k ) = 0 − u ( w i , k ) + u ( v i ) \tau(w_{i,k})=0-u(w_{i,k})+u(v_i) τ ( w i , k ) = 0 − u ( w i , k ) + u ( v i ) . Since τ \tau τ is stable, τ ( w i , k ) < d ( w i , k ) = 1 \tau(w_{i,k})<d(w_{i,k})=1 τ ( w i , k ) < d ( w i , k ) = 1 , i.e. τ ( w i , k ) = 0 \tau(w_{i,k})=0 τ ( w i , k ) = 0 , and hence u ( w i , k ) = u ( v i ) u(w_{i,k}) = u(v_i) u ( w i , k ) = u ( v i ) : in total, each w i , k w_{i,k} w i , k has passed on every chip it has received. The in-neighbours of v i v_i v i are the vertices w i − 1 , k w_{i-1,k} w i − 1 , k , 1 ≤ k ≤ A i − 1 1 \le k \le A_{i-1} 1 ≤ k ≤ A i − 1 , each of which fires u ( v i − 1 ) u(v_{i-1}) u ( v i − 1 ) times. So, with Y i : = u ( v i ) Y_i := u(v_i) Y i := u ( v i ) for 0 ≤ i ≤ n − 1 0 \le i \le n-1 0 ≤ i ≤ n − 1 ,
τ ( v i ) = M 0 ( s i ) − A i Y i + A i − 1 Y i − 1 = ( M 0 + C ⋅ Y ) ( s i ) . \tau(v_i) = M_0(s_i) - A_iY_i + A_{i-1}Y_{i-1} = (M_0 + C \cdot Y)(s_i). τ ( v i ) = M 0 ( s i ) − A i Y i + A i − 1 Y i − 1 = ( M 0 + C ⋅ Y ) ( s i ) .
Since τ \tau τ is a stable configuration, 0 ≤ τ ( v i ) < d ( v i ) = A i 0 \le\tau(v_i) < d(v_i) = A_i 0 ≤ τ ( v i ) < d ( v i ) = A i for all i i i . So Y ∈ N n Y \in\mathbb{N}^n Y ∈ N n , and M 0 + C ⋅ Y M_0 + C \cdot Y M 0 + C ⋅ Y is a dead marking of N N N . By Lemma 3.3 , (1)⇔ \Leftrightarrow ⇔ (6), M 0 M_0 M 0 is not live.
The second part of the proof does not translate the game back into a firing sequence of N N N step by step. This would not be straightforward: in a legal game, a vertex w i , k w_{i,k} w i , k may keep its chip for a long time while other vertices fire. Counting how often each vertex fires avoids this difficulty, just as the state equation records only how often each transition occurs.
Example 5.3. Let N N N be the token-conserving ring with n = 2 n = 2 n = 2 and weights A 0 = 2 A_0 = 2 A 0 = 2 , A 1 = 3 A_1 = 3 A 1 = 3 ; its digraph G N G_N G N is shown in Figure 4 . For M 0 = ( 3 , 0 ) M_0 = (3, 0) M 0 = ( 3 , 0 ) , the only active vertex is v 0 v_0 v 0 . Firing it leaves 1 chip on v 0 v_0 v 0 and puts 1 chip on each of w 0 , 1 , w 0 , 2 w_{0,1}, w_{0,2} w 0 , 1 , w 0 , 2 ; these two vertices fire, and v 1 v_1 v 1 receives 2 chips. Now v 0 v_0 v 0 has 1 < 2 1 < 2 1 < 2 chips, v 1 v_1 v 1 has 2 < 3 2 < 3 2 < 3 chips, and all vertices w i , k w_{i,k} w i , k are empty, so the configuration is stable and σ M 0 \sigma_{M_0} σ M 0 halts. This mirrors ( 3 , 0 ) → t 0 ( 1 , 2 ) (3, 0) \xrightarrow{t_0} (1, 2) ( 3 , 0 ) t 0 ( 1 , 2 ) , where ( 1 , 2 ) (1, 2) ( 1 , 2 ) is a dead marking of N N N . The marking ( 2 , 2 ) (2, 2) ( 2 , 2 ) is live, since
( 2 , 2 ) → t 0 ( 0 , 4 ) → t 1 ( 3 , 1 ) → t 0 ( 1 , 3 ) → t 1 ( 4 , 0 ) → t 0 ( 2 , 2 ) (2, 2) \xrightarrow{t_0} (0, 4) \xrightarrow{t_1} (3, 1) \xrightarrow{t_0} (1, 3) \xrightarrow{t_1} (4, 0) \xrightarrow{t_0} (2, 2) ( 2 , 2 ) t 0 ( 0 , 4 ) t 1 ( 3 , 1 ) t 0 ( 1 , 3 ) t 1 ( 4 , 0 ) t 0 ( 2 , 2 ) returns to ( 2 , 2 ) (2, 2) ( 2 , 2 ) ; correspondingly, for M 0 = ( 2 , 2 ) M_0 = (2, 2) M 0 = ( 2 , 2 ) the configuration σ M 0 \sigma_{M_0} σ M 0 does not halt, and every legal game from σ M 0 \sigma_{M_0} σ M 0 can be continued forever.
Membership in NP. For a digraph G = ( V , E ) G = (V, E) G = ( V , E ) and a vector u ∈ N V u \in\mathbb{N}^V u ∈ N V , let Δ u ∈ Z V \Delta u \in\mathbb{Z}^V Δ u ∈ Z V be given by ( Δ u ) ( x ) : = d ( x ) u ( x ) − ∑ y : ( y , x ) ∈ E u ( y ) (\Delta u)(x) := d(x)u(x) - \sum_{y:(y,x)\in E}u(y) ( Δ u ) ( x ) := d ( x ) u ( x ) − ∑ y : ( y , x ) ∈ E u ( y ) . By the counting argument in the proof of Proposition 5.2 , a legal game from σ \sigma σ in which every vertex x x x fires u ( x ) u(x) u ( x ) times leads to the configuration σ − Δ u \sigma- \Delta u σ − Δ u . The following lemma is the chip-firing counterpart of Lemma 3.1; it is known as the least action principle (cf. [15 Lemma 2.3] for sandpiles on Z d \mathbb{Z}^d Z d , and [4 ] for abelian networks, which include chip-firing on digraphs).
Lemma 5.4 (least action principle). Let σ \sigma σ be a chip configuration on a digraph G = ( V , E ) G = (V, E) G = ( V , E ) , and let u ∈ N V u \in\mathbb{N}^V u ∈ N V be such that ( σ − Δ u ) ( x ) < d ( x ) (\sigma- \Delta u)(x) < d(x) ( σ − Δ u ) ( x ) < d ( x ) for every vertex x x x with d ( x ) ≥ 1 d(x) \ge1 d ( x ) ≥ 1 ; negative entries of σ − Δ u \sigma- \Delta u σ − Δ u are allowed. Then in every legal game from σ \sigma σ , every vertex x x x fires at most u ( x ) u(x) u ( x ) times. Consequently, σ \sigma σ halts iff such a vector u u u exists.
Proof. Suppose that in some legal game from σ \sigma σ some vertex fires more often than this, and consider the first firing in it at which a vertex x x x fires for the ( u ( x ) + 1 ) (u(x)+1) ( u ( x ) + 1 ) -st time. Before this firing, x x x has fired u ( x ) u(x) u ( x ) times and every in-neighbour y y y of x x x at most u ( y ) u(y) u ( y ) times, so x x x carries at most σ ( x ) − d ( x ) u ( x ) + ∑ y : ( y , x ) ∈ E u ( y ) = ( σ − Δ u ) ( x ) < d ( x ) \sigma(x) - d(x)u(x) + \sum_{y:(y,x)\in E}u(y) = (\sigma- \Delta u)(x) < d(x) σ ( x ) − d ( x ) u ( x ) + ∑ y : ( y , x ) ∈ E u ( y ) = ( σ − Δ u ) ( x ) < d ( x ) chips and is not active, a contradiction. So if such a vector u u u exists, every legal game from σ \sigma σ is finite; hence firing active vertices as long as possible leads to a stable configuration, and σ \sigma σ halts. Conversely, if a legal game from σ \sigma σ ends in a stable configuration τ \tau τ , let u ( x ) u(x) u ( x ) be the number of firings of x x x in it; then τ = σ − Δ u \tau= \sigma- \Delta u τ = σ − Δ u , and τ ( x ) < d ( x ) \tau(x) < d(x) τ ( x ) < d ( x ) for every vertex x x x with d ( x ) ≥ 1 d(x) \ge1 d ( x ) ≥ 1 .
Corollary 5.5. The Halting Problem for Chip-Firing is NP-complete on simple digraphs. It is NP-hard in the strong sense already for strongly connected digraphs, namely for the digraphs G N G_N G N of Construction 5.1, in which all but n n n vertices have out-degree 1, and for configurations whose numbers of chips are bounded by a polynomial in the number of vertices.
Proof. Membership in NP. By Lemma 5.4, σ \sigma σ halts on G = ( V , E ) G=(V,E) G = ( V , E ) iff there is u ∈ N V u\in\mathbb{N}^{V} u ∈ N V with ( σ − Δ u ) ( x ) ≤ d ( x ) − 1 (\sigma-\Delta u)(x)\le d(x)-1 ( σ − Δ u ) ( x ) ≤ d ( x ) − 1 for every vertex x x x with d ( x ) ≥ 1 d(x)\ge1 d ( x ) ≥ 1 . With a slack variable for each of these inequalities, this becomes a system of linear equations with non-negative integer unknowns, as in the proof of Proposition 3.5 ; it has at most ∣ V ∣ |V| ∣ V ∣ equations and 2 ∣ V ∣ 2|V| 2∣ V ∣ unknowns, and all its coefficients and right-hand sides have absolute value at most ∣ V ∣ + max x σ ( x ) |V|+\max_x\sigma(x) ∣ V ∣ + max x σ ( x ) . By the theorem of Papadimitriou [24 Theorem, p. 767] , if the system has a solution, it has one whose entries have polynomially many bits. Such a u u u can be guessed and checked in polynomial time. (For strongly connected multigraphs, membership in NP is [14 Cor. 3.2] .)
Hardness. We reduce 3-SAT, as in the proof of Theorem 4.6 . Given a formula φ \varphi φ , let ( N , M 0 ) (N,M_0) ( N , M 0 ) be the marked ring R ( I ( φ ) , W ) R(I(\varphi),W) R ( I ( φ ) , W ) constructed there; then φ \varphi φ is satisfiable iff M 0 M_0 M 0 is not live. All weights A i A_i A i of N N N and all token numbers M 0 ( s ) M_0(s) M 0 ( s ) are bounded by a polynomial in the number n n n of places, and n n n is polynomial in the size of φ \varphi φ . Hence G N G_N G N , which has n + ∑ i A i n+\sum_i A_i n + ∑ i A i vertices, and σ M 0 \sigma_{M_0} σ M 0 can be computed in polynomial time, and the numbers of chips in σ M 0 \sigma_{M_0} σ M 0 are polynomially bounded. By Proposition 5.2 , σ M 0 \sigma_{M_0} σ M 0 halts on G N G_N G N iff M 0 M_0 M 0 is not live, i.e. iff φ \varphi φ is satisfiable.
This answers the question of Farrell and Levine and the question in [12 ] , and confirms the conjecture recorded in [11 ] . Note the role of strong hardness in Theorem 4.6 : replacing a weight A i A_i A i by A i A_i A i parallel paths takes polynomial time only because the weights are polynomially bounded.
Concluding remarks
Liveness of weighted T-systems is coNP-complete, and it is coNP-hard in the strong sense already for single circuits, even when they are token-conserving; so, unless P = NP, it can be decided neither by a polynomial nor by a pseudo-polynomial algorithm. As a consequence, the halting problem for chip-firing is NP-complete on simple digraphs. A later version of this paper is planned to contain further results on reversibility and reachability of ring nets and on tractable special cases, as well as details of the computational cross-checks mentioned in the Introduction.