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
Thirty years ago today, the Voyager 1 spaceprobe had completed its ncounters with the outer planets and was careening out of our solar system. The time came to shut off the probes’ cameras to preserve power and memory for the other onboard scientific instruments. But before engineers flipped the switch, one last photo opportunity was […]
While scientists have studied Moon rocks for 50 years, researchers have for the first time conducted deep analysis on a single grain of lunar dust, atom by atom. Using a common materials science technique called atom probe tomography that’s not widely used by geologists, the Chicago Field Museum’s Jennika Greer and colleagues probed the grain […]
This is so amazing. Watch what happens when a blacksmithing anvil is lowered into a large vat of pure liquid mercury. Update: One of our readers posted the link to the original video in the comments. I have replaced the animated GIF. Thanks, Crispy75. [H/t Alberto Gaitán via Bryce Lynch] Image: Screengrab from GIF
Assembling a truly autonomous smart home is getting closer and closer to reality every day. But for every new smart bulb, thermostat, home security system and appliance we set loose within our walls, there are still probably a half dozen “dumb” items we’d still love to replace. But whether they’re too costly or too big […]
With so many manufacturers out there these days, it’s tough to know who to trust in the ultra-competitive wireless earbuds market. If you’ve never heard of LinearFlux, you may soon. That’s because it’s a company with a stellar pedigree whose co-founders were two of the engineers behind the original success of two audio houses you […]
Two-thirds of American adults drink coffee every day. On average, they’re each drinking about three cups per day, which works out to nearly 400 million cups downed each and every day. We don’t have stats on what percentage of those cups are God awfully bad, but you have to assume with so many ways to […]