[Solved]: What complexity class would this version of generalized chess fall?

Problem Detail: 

By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game). For this decision problem, would it fall in NP, because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

Asked By : rb612

Answered By : Tom van der Zanden

because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

It is possible that generalized chess is in $NP$. We do not have a proof that $NP \not = EXPTIME$ or a proof that a certificate for generalized chess would take an exponential amount of steps. It is highly likely, though.

But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game).

This is unknown. It is known that if two players work together to reach a given position then this may take an exponential amount of moves but this doesn't apply to the specific case of whether white can win and doesn't allow us to conclude whether the problem is in $NP$ or not (because even if it takes an exponential amount of moves, maybe there is a "smarter" certificate that can prove this exponential sequence of moves exists in polynomial time).

because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

No. Shortest path can be solved in exponential time (polynomial time even) and is in $NP$, but it's (likely) not $NP$-complete. Moreover, it is possible that there are problems that require exponential time to be solved and are in $NP$, but that are not $NP$-complete, see e.g. $NP$-intermediate.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/58156