NP-hardness of Circuit Distance for polygons
Statement
Let be a polytope defined by a matrix and a vector , let and be vertices of , and let . A circuit walk is a walk from to whose steps follow circuit directions of . The conjectured decision problem asks whether there is a circuit walk from to of length at most .
Circuit Distance conjecture. The Circuit Distance problem is NP-hard for polygons.
The paper notes that the proof techniques for monotone circuit walks seem likely to extend to the undirected setting but require technical innovation; the claimed NP-hardness for polygons therefore remains open in the supplied source.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.