4
$\begingroup$

From this question, I had the debate about how problems harder than NP are proved.

I said that intuitively I understand it as (from this video explaining that some problems are provably harder than NP):

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.

And a user replied:

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.

I'll admit I'm still new at this and the user that wrote the above comment has much more experience in the field than I do. So I trust this user is correct. However, the explanation the video gave seems very intuitive. But can anyone explain why the video's explanation is wrong?

My thought process is as-follows. One of the definitions of NP is "the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes"." So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win. This cannot be done in less than exponential time and thus is provably harder than NP.

Improve this question
$\endgroup$
6
  • $\begingroup$ I'm not sure that video is correct. Is the roadblock problem EXPTIME-hard? There is no proof that $NP \neq EXPTIME$. $\endgroup$
    – jmite
    Jun 3, 2016 at 4:56
  • $\begingroup$ @D.W. I edited to add my thought process. I believe I understand NP and NP-completeness well. The guy in the video is teaching an entire online course on computational complexity, which I took, and what you are saying directly contradicts what he is saying. So I'd like a thorough explanation for why he is wrong. On top of that, there is proof that chess is EXP-hard, so how is this provable if what I explained above is invalid? sciencedirect.com/science/article/pii/0097316581900169 $\endgroup$
    – rb612
    Jun 3, 2016 at 5:05
  • 2
    $\begingroup$ Once again, you're making the assumption of "I've found one algorithm that solves this problem in exponential time, so the problem must need exponential time." And, since we don't know that NP and EXP are different, we don't know how to prove that, say, generalized chess (which is EXP-complete) is harder than NP. Or do you just mean "Provably complete for a class which, by the way, we think is harder than NP"? In that case, we prove completeness by the usual method: prove that it's in the class and everything in the class reduces to it. $\endgroup$
    – David Richerby
    Jun 3, 2016 at 5:14
  • 1
    $\begingroup$ @DavidRicherby I think I understand it better now. Thanks. It's just that this type of decision problem where you're checking if white can always force a win has an exponential amount of possibilities. In order to verify the proof, every single possibility has to result in a forced win. So you're saying there might exist an algorithm then that can know that every single possibility would result in a forced win but do this in polynomial time, yes? And that's the creative part I'm lacking. $\endgroup$
    – rb612
    Jun 3, 2016 at 5:52
  • 1
    $\begingroup$ @rb612 Exactly. I've no idea if there really is an algorithm that can do that, but nobody's proven that there isn't. $\endgroup$
    – David Richerby
    Jun 3, 2016 at 7:27

2 Answers 2

Reset to default
5
$\begingroup$

The fault lies in this statement:

So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win.

The second sentence might be right, but it might not. Perhaps there is a cleverer, faster way that the verifier can check a certificate, or a cleverer format for the certificate that makes it easy to check. How do we know that's impossible? We don't. That would need proof.

The argument has made an assumption about how a verifier "would have to" behave, without substantiating or proving that assumption. This is basically an argument from failure of creativity: "I can't think of any other strategy a verifier could plausibly use, so there must not exist any valid strategy". Needless to say, this is not a persuasive form of argument.

For instance, let me give you an example. Suppose we replace "generalized chess" by "generalized tic-tac-toe", which works as follows: we have a nxn game board, and the first person to get three in a row wins. Try working through the same argument. It's tempting to draw the same conclusion, that generalized tic-tac-toe is NP-hard. But there are reasons to doubt that conclusion: for instance, this form of generalized tic-tac-toe is always a first-player win when you start from the empty board, for all $n>3$.

There are better examples. In particular, there are games where there are in fact polynomial-time algorithms to play optimally, but the algorithm/strategy is not at all obvious, and if you weren't already aware of it, you might be inclined to be persuaded by the above reasoning that the game is NP-hard. Examples include Nim, Brussels Sprouts, and Wythoff's game. This illustrates that the line of reasoning can't possibly be right -- it leads you to draw conclusions that are false.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Generalized tic-tac-toe can't always be a first-player win, since the $n=3$ case is a draw. Maybe it's a first-player win for all sufficiently large $n$ or something like that? As an aside, generalized go-moku (essentially the five-in-a-row version of generalized tic-tac-toe) is PSPACE-complete. Any idea what is the complexity of the four-in-a-row version? $\endgroup$
    – David Richerby
    Jun 3, 2016 at 5:17
  • $\begingroup$ This is a great explanation! Thanks! And this all makes sense. Please tell me if I'm correct: so the first conclusion I've drawn is when the guy in the video said that there are problems provably harder than NP, he does not mean they are not in NP, just complete in a complexity class that is conjectured to be harder than NP. Second, am I correct in assuming that the only way to verify the decision problem is by iterating over every possible situation and checking if white can force a win? But it's just the algorithm that would do this could run in nondeterministic polynomial time? $\endgroup$
    – rb612
    Jun 3, 2016 at 5:20
  • 1
    $\begingroup$ @DavidRicherby, see edit. To be fair, maybe Tic-tac-toe isn't the ideal example, since I don't know what it's complexity is for arbitrary board positions. For the 4-in-a-row variant in a $m\times n$ board, I don't know if its complexity is known for arbitrary positions, but apparently it's known that starting from an empty board it's a first-player win for $m\ge 30$ and $n=4$. en.wikipedia.org/wiki/M,n,k-game#Specific_results $\endgroup$
    – D.W. ♦
    Jun 3, 2016 at 5:24
  • $\begingroup$ @rb612, your first question: see cs.stackexchange.com/q/9063/755 or stackoverflow.com/q/6712278/781723. I encourage you to use search before asking questions -- often you'll find lots of information about it! your second question: No. That's exactly the failure of creativity type of argument that David Richerby and I are warning you about, I'm afraid. $\endgroup$
    – D.W. ♦
    Jun 3, 2016 at 5:25
  • $\begingroup$ @D.W. oh yeah, sometimes I'm not exactly sure what to look up, but that does help (I kept looking up verifiable, not decidable). But regarding my second question: I want to understand, I'm just having trouble and am frustrated. Sorry. So you are saying that there's a possibility until we prove NP does not equal EXP that an algorithm can exist that checks if white could force a win without actually having to iterate through every single branch, and in polynomial time? $\endgroup$
    – rb612
    Jun 3, 2016 at 5:34
-3
$\begingroup$

Usually running time analysis is applied to algorithms, not applications. It is possible there is some as-yet undiscovered algorithm that solves chess in polynomial time.

The reference to chess being "NP complete" assumes a tree-search algorithm, such as minimax, is being used. Brute force minimax runs in exponential time. For example, even if there are only two choices every move, then the size of the tree is a $2^N$ where N is the number of moves. Exponential running time is considered non-polynomial. (a polynomial algorithm has a running time $a_1N^b + a_2N^{b-1} + a_3N^{b-2} + ...$, where a and b are constants).

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ As chess is EXPTIME-complete, there is definitely no polynomial time algorithm. $\endgroup$
    – Tom van der Zanden
    Jun 3, 2016 at 10:02
  • 1
    $\begingroup$ -1 Along with the reason from @Tom's comment, NP-completeness of a problem does not depend on what algorithm you decide to use to solve it and has nothing to do with the existence of exponential time algorithms. And "exponential running time is considered non-polynomial" makes it sound like a matter of opinion. Any exponential function provably grows faster than any polynomial function. $\endgroup$
    – David Richerby
    Jun 3, 2016 at 10:27
  • $\begingroup$ @TomvanderZanden How do you know that? At one time the Knight's Tour was considered to be non-computable also, but now it is easily solved. Just because we know of no polynomial algorithm to determine the outcome of a position now, does not mean one might not be found in the future. To repeat myself, ALGORITHMS have running times. Problems do not have running times. The same problem can often be solved by DIFFERENT algorithms each of which has different running times. $\endgroup$
    – Tyler Durden
    Jun 3, 2016 at 13:28
  • $\begingroup$ Without the $50$ moves rule, please read. if you have polynomial algorithm to solve the chess game, well that would collapse $P = EXPTIME$, so this is one of this rare moments, where probability is indeed equal $0$... $\endgroup$
    – Evil
    Jun 3, 2016 at 15:36
  • $\begingroup$ I'm told there is a new 75 move rule in chess tournaments now: After 50 moves with no piece taken and no pawn moved, the player may demand a draw, which meant a game could continue for a very, very long time if both players believed they still had a chance to win. Now there is a rule that after 75 such moves the game is a draw (I checked, in force since 1st of July 2014). So the number of moves is strictly limited, and chess can be solved in constant time. The constant is huuuuuuuuuuge. $\endgroup$
    – gnasher729
    Nov 10, 2018 at 18:43

Your Answer

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

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