NP complete problem is hard to solve but when you got the answer it is very easy to check. For example, factorisation of numbers, if I will give you number which is product of two very big prime numbers it will be hard for you to find which numbers are those, but if I will tell you at least one you will be able to check it immediately. So yes chess is not NP complete. (Link to the video I provided in the article says the same ¯\_(ツ)_/¯)
The link you provided mentions PSPACE. Here is comparison of NP-complete vs PSPACE-complete.
However, if that's not the lens you're looking through, then (based on the suspicion that NP ≠ PSPACE) there's a difference between NP-completeness and PSPACE-completeness. If a problem is NP-complete, then even if you can't solve the problem efficiently, you can still check "yes" answers efficiently. On the other hand, if NP ≠ PSPACE and you have an instance of a PSPACE-complete problem you're convinced has a "yes" answer, there might not be any efficient way to convince someone else of this.
This quote says basically the same. For NP-complete problem it is easy to confirm the correctness of answer for PSPACE-complete it is hard to "convince" the correctness of given answer.
Based on my link and your comment, I'm still not certain that all that applies to a single board position, which has a very limited number, even a countable number, of possible moves. So, whether a move is the "best" is going to depend on your definition of "best" (there's that same pernicious relativity we keep hitting in regards to "bad code".)
If we're talking about "the move that is going to create the least immediate disadvantage" (minimizing the value of the pieces at risk of immediate loss), that's definitely P.
If we're talking about "in the context of the whole game", it would depend on the number of moves out from the end of the game, because (off the top of my head), the number of possibilities to be analyzed for, say, three moves from checkmate would be the possible moves for this turn times the possible moves for next turn, so on and so forth. (Not strictly calcuable, mind you, since the number of possible moves changes depending on the previous term. NP again.)
In other words, a chessmaster could easily explain whether a move is "best" in the context of endgame. That's not even remotely NP. I think that's precisely why there are entire books of endgames to study.
But the entire game of chess from the start is NP-hard (although not NP-complete, as I cited.)
For anybody who reads this conversation and not sure what is NP-hard vs NP-complete:
This means that NP-hard problems might be in NP, or in a much higher complexity class, or they might not even be decidable problems. That's why people often say something like "NP-hard means at least as hard as NP" when trying to explain this stuff informally.
The halting problem is a good example of an NP-hard problem that's clearly not in NP
In other words, a chessmaster could easily explain whether a move is "best" in the context of endgame.
It makes a lot of sense from chess player point of view to study endgames and openings, but this logic doesn't apply to study of complexity. Talking about endgames is like comparing sort algorithms for almost sorted arrays. Nobody interested in that.
"It depends" applies to common knowledge, like subject of this article (what is bad code), but I don't think it applies to scientific or mathematical discussion. (Unless we are talking about philosophical interpretation, but we are not in that situation anyway).
To be fair I already lost the thread of conversation...
Well, I don't want to lose context. I was referring to what you said in the article.
...the same way as it is hard to say if this is the best chess move or not (I can give you an answer, but how you gonna know it is true, it is hard to test).
There are some values of "best move" which can be quantifiably stated and proven. In the same way, there are some values of "good code" and "bad code" which can be quantifiably stated and proven. Just because the sum total is NP-hard or NP-complete doesn't mean that all parts therein are also NP.
In any case, thoroughly interesting conversation! Thanks.
P.S. "Almost sorted" actually does make for some interesting sorting algorithmic efficiency discussions. There are forms of "almost sorted" that actually bring out inefficiencies in certain sorting algorithms.
I mean obviously in some case it is provable, like one move before checkmate. But I talked about general case, the same way as you talk about worst case in big O notation...
Yes, and if we go alllllllllllll the way back to the original topic of the article, some "bad code" situations are provable. It is not entirely subjective.
A second pass on this. THIS is bad code because it is ambiguous to the reader.
8 / 2(2 + 2)
There's a big internet argument as to whether it's 1 or 16, and it is bad code because there are multiple justifiable results from it, and the next person to come on the code may have a different interpretation.
but to me this seems like outlier, rather than typical example
I provided you an entire list of quantifiably "bad code" principles in my other comment. None of them are outliers, IME; I've yet to find a single contradiction to any of them in any discussion about coding practice. :)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
NP complete problem is hard to solve but when you got the answer it is very easy to check. For example, factorisation of numbers, if I will give you number which is product of two very big prime numbers it will be hard for you to find which numbers are those, but if I will tell you at least one you will be able to check it immediately. So yes chess is not NP complete. (Link to the video I provided in the article says the same
¯\_(ツ)_/¯)The link you provided mentions PSPACE. Here is comparison of NP-complete vs PSPACE-complete.
This quote says basically the same. For NP-complete problem it is easy to confirm the correctness of answer for PSPACE-complete it is hard to "convince" the correctness of given answer.
Thanks for your response. Good insight.
Based on my link and your comment, I'm still not certain that all that applies to a single board position, which has a very limited number, even a countable number, of possible moves. So, whether a move is the "best" is going to depend on your definition of "best" (there's that same pernicious relativity we keep hitting in regards to "bad code".)
If we're talking about "the move that is going to create the least immediate disadvantage" (minimizing the value of the pieces at risk of immediate loss), that's definitely P.
If we're talking about "in the context of the whole game", it would depend on the number of moves out from the end of the game, because (off the top of my head), the number of possibilities to be analyzed for, say, three moves from checkmate would be the possible moves for this turn times the possible moves for next turn, so on and so forth. (Not strictly calcuable, mind you, since the number of possible moves changes depending on the previous term. NP again.)
In other words, a chessmaster could easily explain whether a move is "best" in the context of endgame. That's not even remotely NP. I think that's precisely why there are entire books of endgames to study.
But the entire game of chess from the start is NP-hard (although not NP-complete, as I cited.)
Or to put that another way...
(In spooky voice) It depeeeeeeeeeeeeeends.
For anybody who reads this conversation and not sure what is NP-hard vs NP-complete:
It makes a lot of sense from chess player point of view to study endgames and openings, but this logic doesn't apply to study of complexity. Talking about endgames is like comparing sort algorithms for almost sorted arrays. Nobody interested in that.
People are talking about big O notation (sometimes about big Theta). Right?
"It depends" applies to common knowledge, like subject of this article (what is bad code), but I don't think it applies to scientific or mathematical discussion. (Unless we are talking about philosophical interpretation, but we are not in that situation anyway).
To be fair I already lost the thread of conversation...
Well, I don't want to lose context. I was referring to what you said in the article.
There are some values of "best move" which can be quantifiably stated and proven. In the same way, there are some values of "good code" and "bad code" which can be quantifiably stated and proven. Just because the sum total is NP-hard or NP-complete doesn't mean that all parts therein are also NP.
In any case, thoroughly interesting conversation! Thanks.
P.S. "Almost sorted" actually does make for some interesting sorting algorithmic efficiency discussions. There are forms of "almost sorted" that actually bring out inefficiencies in certain sorting algorithms.
Yes, I know that this thread is addressed to my reference to chess. But what you try to say to me? This is how I see it:
¯\_(ツ)_/¯Where this going?
The overarching point is, you said "you can't prove that X chess move is best." And I just proved that, actually, yes, you can in some cases.
I mean obviously in some case it is provable, like one move before checkmate. But I talked about general case, the same way as you talk about worst case in big O notation...
Yes, and if we go alllllllllllll the way back to the original topic of the article, some "bad code" situations are provable. It is not entirely subjective.
And the chess analogy mirrors that.
Which is my point.
True like this one
A second pass on this. THIS is bad code because it is ambiguous to the reader.
8 / 2(2 + 2)There's a big internet argument as to whether it's 1 or 16, and it is bad code because there are multiple justifiable results from it, and the next person to come on the code may have a different interpretation.
but to me this seems like outlier, rather than typical example
I provided you an entire list of quantifiably "bad code" principles in my other comment. None of them are outliers, IME; I've yet to find a single contradiction to any of them in any discussion about coding practice. :)