Complexity of running and stopping token circuits is coNP-complete and NP-complete
Complexity of liveness in ring Petri nets and of halting in chip-firing on simple digraphs
Computational ComplexityDiscrete MathematicsFormal Languages and Automata Theory
Summary
The paper studies how hard it is to decide whether a cycle of connected parts that move tokens can keep running forever or eventually stop. The authors show that deciding if these token circuits are "live" (keep running) is coNP-complete, meaning it’s quite a difficult problem. They also prove that for a related problem about chip-firing on simple networks, deciding if the process halts is NP-complete. This work answers a previously open question and relies on connections to number theory problems.
What this means in practice
- •For system designers: Know that detecting continuous operation in weighted token circuits is computationally hard, guiding analysis tool design choices.
- •For network modelers: Understand that deciding if chip-firing processes on simple directed graphs will stop is an NP-complete problem, affecting model predictability.
A theory result. No direct application yet.
Authors
Eike Best, Raymond Devillers, Petr Jančar, Matěj Ošťádal
Abstract
A ring Petri net (weighted circuit, cyclic weighted T-system) consists of a single directed circuit with arbitrary positive arc weights. We show that deciding liveness of ring Petri nets is coNP-complete, and that coNP-hardness holds in the strong sense already for token-conserving rings, in which every transition consumes and produces the same number of tokens. The proof is a short reduction from the covering problem for systems of residue classes (the complement of Simultaneous Incongruences). Together with a known reduction to circuits, it follows that liveness of weighted T-systems (weighted marked graphs, synchronous dataflow graphs) is coNP-complete, and coNP-hard in the strong sense. As a further consequence, the halting problem for chip-firing on simple directed graphs is NP-complete, which answers a question of Farrell and Levine. On 7 October 2026, the problem of liveness was posed to the AI model Claude Opus 5.5 (Anthropic), which found the reduction, also suggesting the application to the chip-firing problem, and wrote a first version of this paper; the human authors checked it and, together with the model, revised it iteratively into the present form.