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
Designer Art Donovan writes, “I’m always looking for new and unique inspiration for my lighting commissions and the latest, cutting edge scientific devices offer a boatload of great design inspiration. From the cool, new ‘James Webb Space Telescope’ to the myriad of complex details in the L.H.P.C. at Cern- it’s a cornucopia of rich imagery.”
In 2009, President Obama pledged to “restore science to its rightful place.” He said, “We will not just meet, but we will exceed the level achieved at the height of the space race, through policies that invest in basic and applied research, create new incentives for private innovation, promote breakthroughs in energy and medicine, and […]
It’s hard to fund space exploration research — the commercial applications are speculative and far-off — but there’s never been a better time to study super-efficient, closed-loop botany of the sort that will someday accompany human interplanetary missions, thanks to the need to develop better grow-ops for the burgeoning legal weed market in Canada.
Some people say magic tricks are nerdy and best left to your 12-year-old asthmatic cousin. But others see value in perfecting the slight of hand and showmanship associated with a perfectly executed routine. We’re firmly in the latter camp. And now, we’re giving you the ability to put a few parlor tricks up your sleeve with the Penguin […]
Bluetooth speakers may be convenient to use, but many of them just aren’t that powerful. Sure, it may be fine if you’re seated in front of the speaker. But move across the room, and you may strain to hear what’s coming from those tiny drivers.There’s a reason why the G-BOOM Wireless Bluetooth Boombox (now $79.99 in the Boing […]
If you’re working to build your web programming knowledge, you know you have a lot of ground to cover. With literally dozens of languages, platforms and environments available to coders, mastering all those technologies can be a daunting task.Up-and-coming coders can start learning some of the most fundamental programming study areas with this Web Hacker course bundle – and […]