7
$\begingroup$

I have a hole in my understanding of what makes a problem NP.

I understand that Mario, for example, is NP-hard - it can be reduced to the NP-complete problem of 3SAT (see https://www.youtube.com/watch?v=mr1FMrwi6Ew)

Therefore if these games were also in NP, they would be NP-complete (by definition).

My understanding is that NP problems can be solved in polynomial time by a nondeterministic turing machine that "guesses" each step correctly. Why isn't this the case for Mario, Chess, and Go? Can't such a machine just guess the right way, for example, for Mario to go at each gadget thus rendering the problem in NP (and thus NP-complete)?

$\endgroup$
2
  • $\begingroup$ Actually they could be NP-complete, if certain things collapse like NP = PSPACE, etc. (since a generalized version of Super Mario Bros is PSPACE-complete) but I wouldn't hold my breath on that happening. $\endgroup$
    – Ryan
    Feb 23 '17 at 14:57
  • $\begingroup$ I think you should say "3SAT can be reduced to Mario" instead of "Mario can be reduced to 3SAT" to conclude that Mario is NP-hard. Am I right? $\endgroup$ Aug 17 at 21:08
8
$\begingroup$

It's a common misconception that chess is NP-hard. Generalized chess may be NP-hard. Chess has an 8x8 board, generalized chess has an nxn board with many pieces.

The question then becomes if generalized chess is NP-complete. I reason that it's not NP-complete; not because it's easier than NP-complete problems but because it's harder. So I'll reason it's outside NP:

Given a certain position on an nxn board, will white win if both players play perfectly? There may be a "yes" answer and the certificate for NP might be a list of perfect moves for both players, but it's intractable to check if those moves by black are actually perfect. Maybe black has better moves so that white doesn't win. You can't check such a certificate in polynomial time.

Also, it may even be the case that a game takes an exponential number of moves, so that such a certificate is of exponential length.

$\endgroup$
3
  • $\begingroup$ "You can't check such a certificate in polynomial time." This doesn't matter as NP-hard does not imply that the problem itself is in NP. It only means that all problems in NP can be reduced to it in polynomial time. NP-complete, on the other hand, would require this. $\endgroup$
    – idmean
    Jul 14 at 13:17
  • $\begingroup$ @idmean I'm not talking about NP-hardness there, I'm talking about NP-(Complete)ness. That reasoning with the certificate suggests that the problem is not NP(-complete), which answers OP's question. The thus implied NP-hardness is a less relevant byproduct. I edited the question to make more clear when I'm talking about NP-hardness and when I'm talking about NP-(complete)ness. $\endgroup$ Jul 14 at 14:48
  • $\begingroup$ I came here by googling "chess np hard" so I was badly framed. Your original answer makes more sense after rereading the original question, but your edit is definitely an improvement for future readers. $\endgroup$
    – idmean
    Jul 14 at 15:04
7
$\begingroup$

Your understanding of what makes chess NP-Hard is slightly flawed. Yes, a nondeterministic machine is able to "play perfectly". But the language of chess is,

$$Chess = \{Pos \quad | \quad \text{White wins with perfect play on an }n\times n \\ \text{ chess board, starting from position } Pos \quad \}$$

Does a certificate for this exist? Consider even just two moves, with white moving first. Then you ask whether a move for white exists such that white wins, for all moves of black. Let $W$ be a program that takes as input a board position and returns yes iff white has won. Then to check whether white wins with perfect play within four moves, you need to evaluate

$$\exists w_1\colon \forall b_1\colon \exists w_2\colon \forall b_2\colon W(Move(Pos, w_1,b_1,w_2,b_2)) $$

But a nondeterministic Turing Machine can only answer questions if you ask them in the form

$$\exists y\colon M(x,y) $$

Hence what makes chess, and other games, hard, is that the quantifiers alternate. From Even and Tarjan [1], who proved, to my knowledge, PSPACE-Completeness of a game for the first time:

Our construction also suggests that what makes "games" harder than "puzzles" (e.g. NP-Complete problems) is the fact that the initiative ("the move") can shift back and forth between the players. Such a shift corresponds to an alternation of quantifiers in the Boolean formula (the NP-Complete problems correspond to Boolean formulas with no quantifier alternation).

[1] Even, Shimon, and Robert Endre Tarjan. "A combinatorial problem which is complete in polynomial space." Journal of the ACM (JACM) 23.4 (1976): 710-719.

$\endgroup$
4
  • $\begingroup$ @ Lieuwe Vinkhuijzen when you said " does a certificate for chess exist " did you mean certificate exist but not of polynomial size in the input ? $\endgroup$
    – user35837
    Feb 23 '17 at 15:23
  • 1
    $\begingroup$ @Shivd Yes. A certificate for any language in $RE$ exists: it is the computation history of a TM for that language halting and accepting the input. But that's too long, and I can come up with that myself, so it's hardly helpful. In a similar vein, a certificate could enumerate all possible moves for black, and give you the perfect move for white. But I only have a polynomial amount of time, so I don't have time to read that certificate! Hence I should become convinced by reading only a polynomial chunk at the start of it. $\endgroup$ Feb 25 '17 at 12:21
  • $\begingroup$ @Shivd Extra credit: What happens when you are allowed to give the wrong answer sometimes, but not too often, and you are given random access (RAM, i.e. query access) to the certificate, so that the certificate can be of exponential size? Crazy things, you get NEXP! See the PCP Theorem $\endgroup$ Feb 25 '17 at 12:25
  • $\begingroup$ Thanks for your helpful answer. I have a question about Super Mario Bros.: Where does the alternation of quantifiers arise? Isn't it a single-player game? Or is the computer the second player? If so, are the actions of the computer player determined from the beginning of the game so that we can still regard SMB as a single-player game? $\endgroup$
    – hengxin
    Jun 3 '19 at 3:57
1
$\begingroup$

My understanding is that NP problems can be solved in polynomial time by a nondeterministic turing machine that "guesses" each step correctly.

That's correct.

Why isn't this the case for Mario, Chess, and Go? Can't such a machine just guess the right way, for example, for Mario to go at each gadget thus rendering the problem in NP (and thus NP-complete)?

You've argued that these problems can be solved by nondeterministic Turing machines but you've not argued that they can be solved in polynomial time on such a machine. How do you know that there's some $k$ such that the outcome of a chess position on an $n\times n$ board can be determined by looking $n^k$ moves into the future?

$\endgroup$
2
  • $\begingroup$ Even when adding "can white win in $n^k$ moves", I still doubt if go and generalized chess can be solved by a nondeterministic turing machine in polynomial time. I think you would need an alternating turing machine for that. $\endgroup$ Feb 23 '17 at 12:27
  • $\begingroup$ @AlbertHendriks That seems likely, yes. $\endgroup$ Feb 23 '17 at 12:30

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.