Intelligent Machines

What Does 'P vs. NP' Mean for the Rest of Us?

A proposed “proof” is probably a bust–but even failed attempts can advance computer science.

Programmers and computer scientists have been buzzing for the past week about the latest attempt to solve one of the most vexing questions in computer science: the so-called “P versus NP problem.”

Vinay Deolalikar, a research scientist at HP Labs in Palo Alto, CA, posted his “proof” online and sent it to several experts in the field on August 6. Colleagues immediately began dissecting the proof on academic blogs and wikis. Early reactions were respectful but skeptical, and the current consensus is that Deolalikar’s approach is fundamentally flawed.

A solid proof would earn Deolalikar fame and fortune. The Clay Mathematics Institute in Cambridge, MA, has named “P versus NP” as one of its “Millennium” problems, and offers $1 million to anyone who provides a verified proof.

But “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. (Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it.)

NP-class problems include many pattern-matching and optimization problems that are of great practical interest, such as determining the optimal arrangement of transistors on a silicon chip, developing accurate financial-forecasting models, or analyzing protein-folding behavior in a cell.

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.

Even if Deolalikar’s proof were found to be sound, then the question remains–what impact would such a proof have on relevant areas of computing?

Superficially, one might think the answer is “not much.” “Proving that P does not equal NP would just confirm what almost everyone already assumes to be true for practical purposes,” explains Scott Aaronson, a complexity researcher at MIT’s Computer Science and Artificial Intelligence Laboratory.

For example, our inability to efficiently factor huge composite numbers (a classic NP problem) forms the basis of modern cryptography–which undergirds everything from national security to purchases. “We don’t need a formal proof that P is not equal to NP in order to rely on the conjecture,” Aaronson says. “Programmers know about the problem and would be excited to see P does not equal NP proved, but on a day-to-day level, they know that reformulating [an NP problem] into something easier makes much more sense than trying to solve the mathematical problem of the century.”

Because NP-class problems are so pervasive (even sudoku puzzles and airline-schedule searches on are computationally “hard”), innovative workarounds are constantly being discovered. Stochastic optimization, for example, mimics the randomness found in physical systems (such as cooling metals or mutating DNA) in order to produce “good enough” solutions instead of computationally hard ones.

Attempts to “cope with” the assumption that P does not equal NP “help us develop new mental technologies,” says Richard Lipton, a computer scientist at Georgia Tech who studies the P versus NP problem. “Even though we’ve been writing algorithms for decades, we don’t fully understand what they’re capable of,” he continues. “So even if you proved that P does not equal NP–something that everyone already believes–it would have to radically expand our understanding of those capabilities, and make many new things possible with computers, in addition to all the clever workarounds we’ve already found.”

So if incremental progress can still generate useful innovation, why aren’t titans of industrial research like Google, Microsoft, and HP (all of whom declined to comment for this article) devoting huge teams of researchers to the P does not equal NP puzzle? “Proving a negative is just incredibly hard, and from [a large company’s] point of view, it probably doesn’t have much impact on the next financial quarter or even the next few years of their business,” says Lipton. “It’s more of a long-term issue.”

Of course, there’s always the alternative: proving that P does in fact equal NP. But don’t hold your breath, says Aaronson. “There are good reasons why very few people believe that P equals NP,” he says. “If it did, we’d be living in a fundamentally different universe, and we’d probably have noticed by now.”

Want to go ad free? No ad blockers needed.

Become an Insider
Already an Insider? Log in.

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe to Insider Premium.
  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look. Exclusive early access to stories.

    Insider Conversations. Listen in as our editors talk to innovators from around the world.

You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.