9
$\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)?

Improve this question
$\endgroup$
5
  • $\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 Dougherty
    Commented Feb 23, 2017 at 14:57
  • 3
    $\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$
    – Carlos Pinzón
    Commented Aug 17, 2021 at 21:08
  • $\begingroup$ Yes @CarlosPinzón, if you reduce (with a not-too-strong reduction, like polytime many-one or logspace) a problem to Mario Bros then Mario Bros is (modulo the reduction you used) harder than that problem. The Cook theorem says that all NP problems reduce to SAT, and even to 3SAT. So to prove NP-hardness of Mario Bros it's sufficient (as polytime reducibility is a transitive relation between languages/decision problems) to prove 3SAT reduces to Mario Bros -appropriately formulated, because it's not obvious what one means by the decision problem "Mario Bros" here. $\endgroup$
    – plm
    Commented Sep 26, 2023 at 8:23
  • 1
    $\begingroup$ As the answers address only (generalized) chess let me note that for the decision problem usually derived from Mario Bros it is not clear whether it is not in NP, thus not NP-complete. I think the standard article is this one: arxiv.org/pdf/1203.1895.pdf . They prove that Donkey Kong Country and Zelda 3 are PSPACE-hard, thus under standard conjectures not NP-hard, and for the Mario games they only prove NP-hardness. A version of Pokemon is NP-complete. Perfect-information Tetris was proved NP-hard in 2002 and in 2020 O(1)-rowed or columned perfect info Tetris was also proved NP-hard. $\endgroup$
    – plm
    Commented Sep 26, 2023 at 8:52
  • 1
    $\begingroup$ I of course meant "under standard conjectures not NP-*complete", as PSPACE-hard implies NP-hard. $\endgroup$
    – plm
    Commented Sep 27, 2023 at 12:24

3 Answers 3

Reset to default
11
$\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.

Improve this answer
$\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
    Commented Jul 14, 2021 at 13:17
  • 1
    $\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$
    – Albert Hendriks
    Commented Jul 14, 2021 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
    Commented Jul 14, 2021 at 15:04
10
$\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.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Feb 23, 2017 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
    Commented Feb 25, 2017 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
    Commented Feb 25, 2017 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
    Commented Jun 3, 2019 at 3:57
  • $\begingroup$ If I took the exact algorithm used by the computer player, and the exact amount of calculation that it does, so that every move I make produces a deterministic response with a fixed number of operations, then it would be in NP. Same with chess against a computer if the computer's moves are deterministic with some limit for the number of operations. Or if the computer is not 100% deterministic but the number of possible outcomes is polynomial or less. $\endgroup$
    – gnasher729
    Commented Jun 2, 2023 at 11:49
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?

Improve this answer
$\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$
    – Albert Hendriks
    Commented Feb 23, 2017 at 12:27
  • $\begingroup$ @AlbertHendriks That seems likely, yes. $\endgroup$
    – David Richerby
    Commented Feb 23, 2017 at 12:30

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