NP Or Not NP?

from the game-theory dept

The Economist (of all places) has a discussion about the challenges of NP-complete problems (such as the famous traveling salesman problem). These problems get much more difficult to solve the more terms you add to the problem. The theory is that figuring out how to solve such a problem would create a method that would solve other such problems - but getting there is not easy (though, it's worth a million dollars to whoever figures it out first). However, some people think that quantum computing will allow quick solutions for NP-problems. The article discusses how Tetris has been determined to be an NP problem, and (jokingly) wonders what Tetris might look like on a quantum computer.

Leave a Comment..