4
$\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?

$\endgroup$
  • 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. Jun 2 '16 at 6:28
  • $\begingroup$ @D.W. Yeah I didn't think of it like that. Good point. $\endgroup$ – rb612 Jun 2 '16 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 Jun 2 '16 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. Jun 2 '16 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 Jun 2 '16 at 7:25
6
$\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.

$\endgroup$
  • $\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 Jun 2 '16 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 Jun 2 '16 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 Jun 2 '16 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 Jun 2 '16 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.

$\endgroup$
  • 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 Jun 2 '16 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 Jun 2 '16 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 Jun 2 '16 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 Jun 2 '16 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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