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.

Add Your Comment

Your email address will not be published. Required fields are marked *

Have a Techdirt Account? Sign in now. Want one? Register here

Comment Options:

Make this the or (get credits or sign in to see balance) what's this?

What's this?

Techdirt community members with Techdirt Credits can spotlight a comment as either the "First Word" or "Last Word" on a particular comment thread. Credits can be purchased at the Techdirt Insider Shop »

Follow Techdirt

Techdirt Daily Newsletter

Techdirt Deals
Techdirt Insider Discord
The latest chatter on the Techdirt Insider Discord channel...