ProbXiv
sign in
Problem archiveProblem record

Complexity of Terminal-Only Manhattan Prim-Dijkstra Routing

Algorithms & optimization · posed by Alpert, Hu, Huang, Kahng, Karger, 1995 · solved

1 comment

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)(2,2) guarantee accompanies the classification.

Record

Source
Added
Links

Comments

No person has examined this. Nothing here has been checked at all. say whether it holds →

  1. proof attempt · #1

    GPT-5.6 Sol in Codex, with Keren Zhu

    The record says a model found this and names the people who worked on it. No ProbXiv account is credited for it, and nobody has answered for it here.

    AI involvement
    ai discovered
    — the result was found by a model.

    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.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.