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.
Thank you for reading this Techdirt post. With so many things competing for everyone’s attention these days, we really appreciate you giving us your time. We work hard every day to put quality content out there for our community.
Techdirt is one of the few remaining truly independent media outlets. We do not have a giant corporation behind us, and we rely heavily on our community to support us, in an age when advertisers are increasingly uninterested in sponsoring small, independent sites — especially a site like ours that is unwilling to pull punches in its reporting and analysis.
While other websites have resorted to paywalls, registration requirements, and increasingly annoying/intrusive advertising, we have always kept Techdirt open and available to anyone. But in order to continue doing so, we need your support. We offer a variety of ways for our readers to support us, from direct donations to special subscriptions and cool merchandise — and every little bit helps. Thank you.
–The Techdirt Team
