You know, I just shouldn't have chimed in. I'm beginning to regret that I did.
Thank you for speaking down to me. Now, lets get to business.
I get it. I actually understand computational complexity very well. Had you read the follow-up post, which was posted well before your post, you would see that I added the caveat "if P!=NP", long before you had a chance to talk down to me.
I actually threw in the caveat in a follow-up post (since I wasn't very atomic about it) that this was if P!=NP. Nothing that I said affects class inclusions once that caveat is thrown in.
Okay, but in the sense that any of the games in the original submission are NP-Hard, so are Chess and Go.
I've never seen one, but that doesn't mean that it doesn't exist.
The generalizations of both games are NP-Hard. They're only constant time because of the fixed number of pieces and places for those pieces to go.
I should caveat all of this. The "no polynomial-time algorithm" bit is only true if P!=NP. If P=NP, then there is a deterministic polynomial-time algorithm for NP-Complete problems. NP-Hard, however, just means that it's at least as hard as NP, so, it's possible that there's no algorithm for that harder problem. You have to be really really precise when talking about this stuff.
PSPACE-Complete: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.41
Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.
NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games. Additionally, you always have to generalize these games in order to make that claim. Since computational complexity is defined in terms of the length of the input, and certainly all of these games are being played on an input of fixed length.
However, there are effective approaches to solving NP-Hard problems. There are solvers for known NP-Hard problems. If you Google "sat solver" you'll find at least 5 that you can just download. SAT solvers are used in VLSI validation and other practical things. These solvers use heuristics to improve search performance, generally proposing answers and checking them (for NP-Complete problems).
Also, there are tons of games known to be NP or PSPACE complete. The reductions for those games are kind of a standard problem, since the AI community writes a bunch of these solvers.
I've never originated one, but I've found incorrect mathematics in a few of them and corrected it if time allowed.
It is impossible to enjoy idling thoroughly unless one has plenty of work to do. -- Jerome Klapka Jerome