4
$\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$
  • $\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
5
$\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 is, 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$
4
$\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$
  • $\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$ – aaag 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$ – Lieuwe Vinkhuijzen 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$ – Lieuwe Vinkhuijzen Feb 25 '17 at 12:25
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$
  • $\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$ – Albert Hendriks Feb 23 '17 at 12:27
  • $\begingroup$ @AlbertHendriks That seems likely, yes. $\endgroup$ – David Richerby 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.