Quantum Avoid True complexity conjecture
Statement
Let $\ruleset{Quantum Avoid True}$ be the quantum extension of the combinatorial game $\ruleset{Avoid True}$, and let a classical start mean that the initial position has no quantum superposition. Let $\ruleset{Quantum Nim}$ be the quantum extension of Nim, and let a poly-wide quantum start mean an initial quantum position whose number of realizations is polynomially bounded.
Quantum Avoid True conjecture. Determining the outcome class of $\ruleset{Quantum Avoid True}$ with a classical start is $\cclass{PSPACE}$-complete. Consequently, determining the outcome class of $\ruleset{Quantum Nim}$ with a poly-wide quantum start is $\cclass{PSPACE}$-hard.
The complexity of Quantum Nim is described as widely open, and this conjecture would establish a strong worst-case lower bound through Quantum Avoid True.
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.