A modular-storage proof of NP-completeness for chip-firing halting on simple digraphs

Abstract

We give a self-contained proof that ordinary conservative chip-firing halting is NP-complete on finite loopless simple strongly connected digraphs. Hardness holds with polynomial numerical total initial chips and a specified vertex whose deletion leaves an acyclic graph of depth at most one. A separate construction forbids antiparallel arcs. The proof combines the primed-toppler mechanism of Holroyd–Levine–Winkler with the classical prime/Boolean/clause encoding of Stockmeyer–Meyer, also reconstructed by Gramlich. We prove the physical conservative realization, its legal checkpoint dynamics and the arbitrary-schedule implication in full; NP membership is credited to Farrell–Levine and reproved with an explicit certificate bound. This is an attributed proof of the historical simple-digraph question. Exact full-result and realization priority and preexisting worldwide openness remain unknown after a bounded audit; no firstness is claimed. AI tools were used extensively. The paper is unrefereed and has not received external human peer review.

The idea in plain English

Place a pile of chips at each vertex of a directed graph. A vertex can fire when it has enough chips to send one along every outgoing arrow. Firing moves chips without creating or removing any. The question is whether the game can eventually reach a position where no vertex can fire.

This paper proves that deciding whether the game halts is NP-complete even when the graph has no loops or repeated arrows and every vertex can reach every other vertex. A separate construction also forbids arrows pointing in opposite directions between the same two vertices.

The difficulty persists with polynomially many initial chips and a graph that becomes very shallow after removing one specified vertex. The construction encodes a Boolean formula through counters that cycle modulo small primes: a stable position can be reached exactly when the formula has a satisfying assignment.

The precise result

The input is a finite loopless simple strongly connected digraph with at least two vertices and an arbitrary nonnegative integer chip configuration encoded in binary. Each vertex fires at its actual outdegree and sends one chip along each outgoing arc. There is no dissipative sink.

HALTING asks whether some finite legal firing sequence reaches a stable configuration. The problem is NP-complete under deterministic polynomial-time many-one reductions. The same conclusion holds for the oriented subclass, which additionally forbids antiparallel arcs.

Hardness holds when a specified root r is supplied and deleting r leaves an acyclic graph with no directed path of two arcs. The reduction also has polynomial numerical total initial chips in the source 3-SAT input length, so the hardness persists when chip counts are written in unary.

Membership in NP covers arbitrary binary chip counts. A certificate records how many times each vertex fires, with polynomially many bits, and certifies a nonnegative stable endpoint. It need not list the full firing sequence.

Why the result holds

A modular bank stores a number of chips that is largest exactly at selected residues. Its priming specializes the established primed-toppler construction of Holroyd–Levine–Winkler. The prime/Boolean/clause encoding is due to Stockmeyer–Meyer and is also reconstructed by Gramlich.

The proof realizes these counters as an ordinary conservative graph. At each checkpoint, every emitted chip has returned to the correct part of the graph. The root becomes unable to fire precisely when all residue conditions hold. The Chinese remainder theorem connects such a checkpoint to a satisfying Boolean assignment.

A legal checkpoint sequence establishes both directions of the reduction. Classical least action relates this sequence to all legal firing orders, without a fairness assumption. The proof also gives an explicit bound for a short firing-count certificate, using the NP-membership method of Farrell–Levine.

Scope and limitations

These are worst-case complexity statements. Unless P = NP, no polynomial-time algorithm solves every valid input. This does not mean that every instance is difficult, and the polynomial-bit certificate does not give a polynomial-time simulation of the game.

The theorem does not claim bounded-degree or Eulerian hardness, and it does not concern a fixed graph, a dissipative-sink model, weighted firing thresholds or a specified target configuration. The oriented construction is separate from the simple construction, which allows antiparallel arcs.

The primed-toppler mechanism, prime-residue encoding, root-last stabilization, least action, tree periods and NP-membership method have prior sources. The paper supplies a complete conservative graph realization and halting reduction with those antecedents credited.

Exact full-result and realization priority remain unknown. A bounded source comparison does not establish that the historical question was still open worldwide immediately before this work. Finite computational checks support the written proof; they do not establish the universal theorem by exhaustion.

Status and AI use

AI tools were used extensively in solving, checking, adversarial review, source comparison, programming and writing. The author is responsible for the claims. The paper has not received external human peer review or journal acceptance and is not formally certified in a proof assistant.

Read the paper

Open PDF in a full window · Download the original from Zenodo

Collaborate on this result

I welcome substantive collaboration on independent mathematical review, comparison with the chip-firing and computational-complexity literature, or preparation for journal submission. Expertise in chip-firing dynamics, abelian networks or exact complexity reductions would be especially useful.

Authorship and responsibilities would be discussed in relation to the substantive contributions made.

Cite this paper

Alec Kriebel. (2026). A modular-storage proof of NP-completeness for chip-firing halting on simple digraphs (Version 1.0) [Preprint]. Zenodo. https://doi.org/10.5281/zenodo.23431716

Download BibTeX

Background and prior work

• Farrell and Levine, CoEulerian graphs: This work states the historical simple-digraph question and proves NP membership. Its least-action and tree-period methods are credited and reproved here at the required scope.
• Holroyd, Levine and Winkler, Abelian logic gates: Lemma 4.1 supplies the primed-toppler mechanism used by the modular-storage construction. The paper does not claim this mechanism as new.
• Stockmeyer and Meyer, Word Problems Requiring Exponential Time: Preliminary Report: Theorem 6.1 contains the classical prime/Boolean/clause encoding. The present proof uses its complementary acceptance formulation.
• Gregor Gramlich, Probabilistic and Nondeterministic Unary Automata: Fact 3 reconstructs the same prime-residue encoding and is explicitly credited as a source.
• Matthew Farrell, The halting problem for chip-firing on finite directed graphs: The thesis supplies prior root-last stabilization and conserved-mass context. Lionel Levine is the thesis adviser, not a coauthor.
• Kimmo Eriksson, No Polynomial Bound for the Chip Firing Game on Directed Graphs: Exponentially long games on simple directed graphs with polynomially many initial chips were already known. A short halting certificate should not be confused with a short simulation.