Comment Not new (Score 1) 117
This was being done at MIT 10 years ago.
http://people.csail.mit.edu/rweiss/
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.
Two-Photon Walk a Giant Leap For Quantum Computing 112
ElectricSteve writes "Research conducted at the University of Bristol means a number of quantum computing algorithms may soon be able to execute calculations of a complexity far beyond what today's computers allow us to do. The breakthrough involves the use of a specially designed optical chip to perform what's known as a 'quantum walk' with two particles ... and it suggests the era of quantum computing may be approaching faster than the scientific establishment had predicted. A random walk – a mathematical concept with useful applications in computer science – is the trajectory of an object taking successive steps in a random direction, be it over a line (with only two possible directions) or over a multi-dimensional space. A quantum walk is the same concept, but translated to the world of quantum computing, a field in which randomness plays a central role. Quantum walks form an essential part of many of the algorithms that make this new kind of computation so promising, including search algorithms that will perform exponentially faster than the ones we use today."
YouTube Explains Where HTML5 Video Fails 426
awjr writes "YouTube have pretty much come down on the side of Flash having major issues with the lack of features that the HTML5 <video> tag has and may never have."
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.
Obama Outlines Bold Space Policy ... But No Moon
455
The Bad Astronomer writes "In front of a mostly enthusiastic audience at NASA's Kennedy Space Center today, President Obama outlined a bold, new space policy. It's a change from his previous policy; the Constellation rockets are still dead, but a new heavy-lift rocket system is funded. He specifically talked of manned asteroid and Mars missions, but also stated there would be no return to the Moon. This is a major step in the right direction, but still needs some tweaking."
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.
Comment Re:chess and go aren't np-hard, but they are also (Score 5, Informative) 322
Chess and Go are actually EXPTIME-complete, even harder than NP-complete problems and PSPACE-complete problems.
In general, one-player games of bounded length (like Flood-It, or Sudoku) tend to be NP-complete; one-player unbounded games (like sliding-block puzzles, or Sokoban) tend to be PSPACE-complete; two-player bounded-length games (like Hex, or Amazons) also tend to be PSPACE-complete, and two-player unbounded games (like Chess, Checkers, and Go) tend to be EXPTIME-complete.
I can't resist here a plug for my book (with Erik Demaine), Games, Puzzles, and Computation, which discusses all these issues in detail. A theme running throughout the book is the same as the view expressed in this paper: most interesting games and puzzles seem to be as hard as their "natural" complexity class, outlined above.
Comment My favorite part of the clip: (Score 4, Funny) 134
"George Takei as Chief Physicist"
Helmsman, swordsman, physicist... the guy can do everything!
What Computer Science Can Teach Economics 421
eldavojohn writes "A new award-winning thesis from an MIT computer science assistant professor showed that the Nash equilibrium of complex games (like the economy or poker) belong to problems with non-deterministic polynomial (NP) complexity (more specifically PPAD complexity, a subset of TFNP problems which is a subset of FNP problems which is a subset of NP problems). More importantly there should be a single solution for one problem that can be adapted to fit all the other problems. Meaning if you can generalize the solution to poker, you have the ability to discover the Nash equilibrium of the economy. Some computer scientists are calling this the biggest development in game theory in a decade."
SCO Terminates Darl McBride 458
bpechter writes "Linux Today reports SCO has terminated Darl McBride and linked to the SCO 8K SEC report. The report found also at the SCO site and states: 'the Company has eliminated the Chief Executive Officer and President positions and consequently terminated Darl McBride.'"
