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
New research on trends in adult human height over the last century confirm that, no surprise, humans are getting taller overall due to better nutrition and disease control. However according to the health science group Non-Communicable Diseases Risk Factor Collaboration (NCD-RisC), the gain in adult height varies dramatically by country. From their paper, published in […]
Between April and July, Iran’s salty Lake Urmia changed from a bright green color to a blood red. NASA’s Aqua satellite captured the image above and reported on the science behind the strange transformation. According to NASA, the periodic color change is caused by micro algae producing carotenoids that help with photosynthesis and act as […]
In the late 1960s and 1970s, the mind-expanding modus operandi of the counterculture spread into the realm of science, and shit got wonderfully weird. Neurophysiologist John Lilly tried to talk with dolphins. Physicist Peter Phillips launched a parapsychology lab at Washington University. Princeton physicist Gerard O’Neill became an evangelist for space colonies. Groovy Science: Knowledge, […]
It’s one thing to enjoy dinner at home and a nice glass of Cabernet Sauvignon with your best friend, Netflix, but it’s another thing entirely to make that meal from scratch and get that wine delivered right to your doorstep.But what if we told you there’s a way to make this possible? To keep your social life, […]
Having to pack and drag your stuff through security can put quite the damper on your vacation plans. Thankfully, we’ve got your back with one way to make traveling more painless: the Jumper Overnighter Travel Bag.This compact bag is so lightweight that you can effortlessly carry it, and fit it into any overhead compartment. But just […]
Learning is a 24/7/365 proposition, and it never ends. And if you’re truly serious about leveling up your skill sets and career prospects, get a subscription to Stone River Academy’s massive course collection. This offer normally is worth over $1,400, but is now available for just $89 in the Boing Boing Store.A respected name in information technology […]