Claude Opus 5.5 找到环 Petri 网活性问题的 coNP 完全性证明
Complexity of liveness in ring Petri nets and of halting in chip-firing on simple digraphs
几个计算复杂度的公开问题被 Claude Opus 5.5 找到了归约证明，人只负责验证和修改，这篇论文本身就成了人机协作做数学的案例。
论文证明环 Petri 网的活性判定问题是 coNP 完全的，且在 token 守恒的环上 coNP 困难性已成立。证明方法是从残差类覆盖问题（Simultaneous Incongruences 的补问题）做归约。由此推出加权 T-系统的活性判定为 coNP 完全，并进一步证明简单有向图上 chip-firing 的停机问题是 NP 完全的，回答了 Farrell 与 Levine 的公开问题。据论文说明，归约方法和 chip-firing 的应用由 Claude Opus 5.5（Anthropic）于 2026 年 10 月 7 日提出并写出初稿，人类作者验证并迭代修改成稿。
Complexity of liveness in ring Petri nets and of halting in chip-firing on simple digraphs
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.
