Comment: Re:Bah. e is better than them all (Score 5, Funny) 241
Comment: Not new (Score 1) 117
http://people.csail.mit.edu/rweiss/
Comment: BeOS (Score 3, Interesting) 312
Left out of that history is the branch that almost happened: for quite a while the smart money was that Apple would buy Be, Inc. and use BeOS as the basis for their future OSes. More than a few developers (myself included) based their business models on this happening.
Comment: !exponential search speedup (Score 1) 112
Grover's search algorithm gives only a quadratic speedup.
Comment: "This fits me perfectly as a Java programmer," (Score 3, Interesting) 109
Exactly. That was the big problem I had with the book: it's written for Java programmers. I am intrigued by the language, but I would much prefer a book that treats the language on its own terms.
Comment: Re:chess and go aren't np-hard, but they are also (Score 1) 322
It's on my list...
Comment: Re:chess and go aren't np-hard, but they are also (Score 4, Interesting) 322
I'll mention it to my publisher, but honestly it would lose a lot without all the color figures.
The book is based on my Ph.D. thesis, which you can download for free:
Comment: Re:I don't get why... (Score 1) 322
The reason that fun games tend to be NP-hard (or harder) is that if a game's "physics" supports interesting constructions requiring complex reasoning to solve, then probably that same physics can be used to build computational gadgets, which is how you show hardness of the generalized version. This quality expresses itself even on small, fixed-size board.
Comment: Re:Just to throw this out there (Score 2, Interesting) 322
Ah, it doesn't mean that either.
If a problem is NP-hard, it means it is at least as hard as any other problem that can be solved in polynomial time on a nondeterministic computer.
It is an open question (P=NP) whether this is equivalent to saying that there is no deterministic polynomial-time algorithm.