Complexity of Terminal-Only Manhattan Prim-Dijkstra Routing
resolvedconfidence 70%
VibeMathed reports this item as resolved. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.
Precise statement
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 $(2,2)$ guarantee accompanies the classification.
The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement
fidelity, correctness, priority, or novelty.
What AI did
GPT-5.6 Sol in Codex
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.
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.
arXiv:2607.17005 - Provably Good Prim-Dijkstra Revisited: New Theory and a Practical Algorithm for a Classical VLSI Routing Problem with LLMs
VibeMathed reports this item as resolved. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.
Known method families
argument (source-reported)
Source-reported tools: argument.
Independent: unknown · difference confidence: 0
What remains uncertain
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.
VibeMath has not independently verified the mathematical claim.
AI-attempt independence and training-data exposure are unknown unless explicitly documented.
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.