Honestly, Slashdot has been one of my favorite websites ever since it was shown to me in high school. Within a year or two after I started reading Slashdot, it became *the* place to become "in the know" with what was going on in technology.

A big part of the direction that Slashdot has moved in has been a product of this. More and more people knew that Slashdot was a place to go to to get "in the know," but the pool of truly enthusiastic, sharp, science and engineering minded people became diluted with people who simply wanted to be associated with that. Everyone wanted to participate, and the signal to noise ratio went down. It's unfortunate, but the thing that initially attracted people here was largely due to your vision and your efforts. I don't believe that your departure is likely to improve the site. I know that I, at times, have been critical of the direction that Slashdot has gone in (and at times you have expressed frustrations with the site yourself, or at least, frustrations with what you should do with it), but this change in direction has largely been a product of the change in readership. It has been your vision that has managed to keep it sane.

What is truly unfortunate is that, looking around the Internet for a site that gives me the same enjoyment that Slashdot did in its heyday, I have come up empty-handed. It really does feel like there is nowhere online for the old-school geek anymore. Everyone wants to be part of that now. In fact, being a "hipster" now involves saying how geeky and quirky you are. It's pretty annoying seeing kids who can't even program move in on my turf like that.

Anyway, thanks for all of the effort that you've put into this site, and I honestly do hope that we meet at an Open Source convention of some sort someday. If we do, I'll buy you a beer.

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.