5
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Your first paragraph is faulty. It has the form "because this one algorithm I thought of takes exponential time, the problem must not be in NP". That's faulty -- maybe there's some other algorithm you haven't thought of that's better. $\endgroup$
    – D.W. ♦
    Commented Jun 2, 2016 at 6:28
  • $\begingroup$ @D.W. Yeah I didn't think of it like that. Good point. $\endgroup$
    – rb612
    Commented Jun 2, 2016 at 6:58
  • $\begingroup$ @D.W. But I have a video that shows (it's on Udacity complexity theory) that there are problems harder than NP provably. youtu.be/sQU_6RCizu4 but yeah your argument makes sense because we don't know if NP equals EXPTIME. So what is this guy talking about in the video then? $\endgroup$
    – rb612
    Commented Jun 2, 2016 at 7:15
  • $\begingroup$ Well, that's a separate question, and best asked separately. This is a question-and-answer site, and comments here are intended only for improving the questions/answers, not for posting new questions or for extended discussion. I suggest you spend some time researching and thinking about that one, and if you're still puzzled, post a new question (and show your reasoning and your efforts to resolve it on your own). $\endgroup$
    – D.W. ♦
    Commented Jun 2, 2016 at 7:22
  • $\begingroup$ @D.W. You're right, but my first paragraph is literally restating what that teacher said in the video. So either I miswrote it or he is wrong. But I guess I can pose this as a separate question. $\endgroup$
    – rb612
    Commented Jun 2, 2016 at 7:25

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer! Could you explain "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"? I'm not quite sure I understand what you mean: wouldnt this prove exactly that it's in NP because the proof could be verified in polynomial time? $\endgroup$
    – rb612
    Commented Jun 2, 2016 at 5:38
  • 2
    $\begingroup$ What I am saying is that the trivial certificate (just list the moves necessary for white to win) might not work since it could be exponentially long. This however, does not rule out that the problem is in $NP$. $\endgroup$
    – Tom van der Zanden
    Commented Jun 2, 2016 at 5:40
  • $\begingroup$ Yep, you're right. If it could be proven what you're saying is actually true, that there exists a certificate that would take exponential time to check, would rule out the problem being in NP? And being EXPTIME-complete, would also prove that NP does not equal EXP? $\endgroup$
    – rb612
    Commented Jun 2, 2016 at 5:57
  • 2
    $\begingroup$ Perhaps it is better if you think about it a bit more, and break out questions you might still have in to separate questions. $\endgroup$
    – Tom van der Zanden
    Commented Jun 2, 2016 at 6:04
1
$\begingroup$

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?

Probably. In fact, I suspect it would be in logspace or perhaps even a smaller complexity class. Determining that white can win involves barely more than checking that the position isn't a stalemate, white isn't already checkmated and white has sufficient material to checkmate (from memory, a queen; a rook; two bishops; three knights; a bishop and a knight; or a pawn, via promotion). That doesn't quite work, since it could be that black's only legal moves unavoidably force checkmate or force the loss of sufficient mating material for white. But it feels pretty close to the truth.

Because the verifiability of this proof would only require polynomial time (just play out the winning game).

That's not true because there's no guarantee that the number of moves required is bounded by some polynomial in the size of the input.

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?

No, that's not the definition of NP-completeness. While it's a reasonable intuition that a problem being NP-complete means that we don't know any algorithms that are better than exponential, NP does not mean "it takes exponential time on a deterministic TM." Being NP-complete means that the problem is in NP and every other problem in NP reduces to it by, say, a polynomial-time many-one reduction.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ (To avoid confusion: I agree with you, and am just pointing out an even stronger possibility.) ​ The problem is at least as hard as thresholds, since it can be that: white's king is on (2,0), black's king is on (0,2), white has a rook or bishop on (3,0), black has a rook or bishop on (0,3), someone has a queen on (1,1), ​ ​ ​ (continued ...) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Jun 2, 2016 at 12:35
  • 2
    $\begingroup$ (... continued) ​ ​ ​ white has some number of queens to the right of that on rank 1, black has some number of queens above that on file 1, and nothing else is on the board. ​ Who wins is determined by who first runs out of queens to take on (1,1) with. ​ However, I don't see any argument against the problem being in rational-uniform TC$_0$. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Jun 2, 2016 at 12:38
  • $\begingroup$ This makes a lot of sense. Thanks! But you say "That's not true because there's no guarantee that the number of moves required is bounded by some polynomial in the size of the input." So do you mean the number of moves could grow exponentially as board size increases, and even the time it would take to check ONE game's outcome could be exponential in time? $\endgroup$
    – rb612
    Commented Jun 2, 2016 at 21:16
  • 1
    $\begingroup$ Could be; isn't necessarily. Also, what does it mean to say "check one game's outcome"? That sounds like the decision problem "given a description of a game, determine whether XXX holds." But, in that case, the game itself is the input and one would measure complexity with respect to the length of that. $\endgroup$
    – David Richerby
    Commented Jun 2, 2016 at 21:19
0
$\begingroup$

But isn't there an upper limit on chess games length?

The fifty move rule that says it's a draw if no pawn positions have been changed for the last fifty moves puts an O(n^3) (pieces needed to be captured, maximum pawn moves, and the capturing of the pawns nnn) bound on game length.

So wouldn't the real chess game even tho generalized should be in PSPACE?

Or does the theory disregard the 50 move rule?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.