Complexity of Terminal-Only Manhattan Prim-Dijkstra Routing
Prim-Dijkstra routing interpolates between a minimum spanning tree and a shortest-path tree, and has been used and improved in VLSI physical design since the early 1990s, but the complexity of the terminal-only Manhattan decision problem was never settled. It is weakly NP-complete. A continuous cost-radius tradeoff with a balanced guarantee accompanies the classification.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Computational complexity
- Posed by
- Alpert, Hu, Huang, Kahng, Karger
- Year posed
- 1995
- Years open
- 31y
- Solved
- 2026-07-18
- Model
- GPT-5.6 Sol in Codex
- Vendor
- OpenAI
- Collaborators
- Keren Zhu
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The paper is a designed experiment rather than an incidental use. One model was run under five deliberately incompatible research conditions that differed in premise and information boundary: construct and adversarially audit an NP-completeness proof from the problem definition alone; pursue a polynomial-time exact algorithm blind, without literature or the option of retreating to a hardness claim; pursue the same informed; assume hardness and seek a bicriteria guarantee; and synthesize the record into a solver against an evaluator frozen beforehand. The hardness track produced the NP-completeness proof. The two exact tracks converged on the same architecture and produced counterexamples rather than a proof, which the author treats as a control.
Verification
Single-author arXiv preprint with a full NP-completeness proof in Appendix A, a released research record, and a partial Lean snapshot whose theorem boundary the paper states explicitly. Not yet peer-reviewed.