P â‰ NP: To begin with. There is (almost) no doubt whatever about that.
Why? To quote Scott Aaronson—an MIT complexity researcher interviewed in an excellent article on Technology Review about the background of the "P vs. NP" problem—if P = NP then, "we'd be living in a fundamentally different universe, and we'd probably have noticed by now."
Naturally, that leads to another, "Why?", which author John Pavlus answers cleanly and clearly:
"P versus NP" is more than just an abstract mathematical puzzle. It seeks to determine--once and for all--which kinds of problems can be solved by computers, and which kinds cannot. "P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked.
The "P versus NP problem" asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.
That's why P vs. NP matters. And it's why P probably â‰ NP. "But wait," you ask, "Wasn't this solved, like, a couple weeks ago."
Sadly, no. The proof offered by HP labs researcher Vinay Deolalikar isn't standing up very well against scrutiny and is not likely, at this point, to earn him the $1 million prize still up for grabs.
Technology Review: What does "P vs. NP" mean for the rest of us?
Some rights reserved by stuartpilbrow
Tiny micromotors about the width of a human hair traveled through a mouse’s stomach delivering antibiotics to treat a stomach ulcer. The motors are powered by bubbles. According to the researchers from the University of California San Diego, the microrobot-based treatment proved more effective than regular doses of the medicine. From New Scientist: The tiny […]
In 1971, astronomer Frank Drake, the father of the search for extraterrestrial intelligence, drew a map pinpointing Earth in our galaxy. That diagram, a “pulsar map,” was etched on a plaque designed by Frank and Carl Sagan and first carried into space in 1972 by the Pioneer 10 and 11 spacecraft. In 1977, the pulsar […]
Last night, NBC Nightly News aired the wonderful video below about the Voyager Golden Record vinyl box set I produced with my friends Tim Daly and Lawrence Azerrad! Forty years ago this month, NASA launched two spacecraft, Voyager 1 and 2, on a grand tour of the solar system and beyond, into the mysteries of […]
The Pry.Me Bottle Opener holds tens of thousands of times its own weight, and you can pick one up now from the Boing Boing Store.This remarkable keychain is considerably smaller than any of your keys, but don’t let that fool you: it can easily open any bottle, and could even tow a trailer full of […]
Guaranteeing your privacy online goes way beyond checking the “Do Not Track” option in your browser’s settings. To ensure that your internet activity is totally hidden from Internet Service Providers, advertisers, and other prying eyes, take a look at Windscribe’s VPN protection. It usually costs $7.50 per month, but you can get a 3-year subscription […]
This project management bundle will help you get organized and learn how to lead a team to success. You can pay what you want for these five courses when you pick them up from the Boing Boing Store.To help you become an invaluable asset for your company, this bundle includes a curated collection of professional […]