The PSPACE-completeness conjecture for Trail Trap
Statement
Consider the decision problem : given a graph, determine whether the second player has a winning strategy in Trail Trap. Trail Trap PSPACE-completeness conjecture. The problem is PSPACE-complete. The paper establishes NP-hardness on connected bipartite planar graphs of maximum degree , but does not prove PSPACE-completeness; the conjectured stronger complexity classification remains open.
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.