Computer science breakthrough: The end of P = NP?

Researchers claim that one of the great unresolved mathematical questions in theoretical computer science just bit the dust

Last week, HP Labs mathematician Vinay Deolalikar started circulating a startling paper that claims to have solved the preeminent open problem in computer science, known as P = NP. Er, more accurately, that P is not equal to NP (P ≠ NP).

If his lengthy, complex, multidisciplinary proof holds up, one of the great unresolved mathematical questions of the 20th century has met its match. And it only took 50 years or so.

[ Get the spin on key tech news that you'll find nowhere else at InfoWorld's Tech Watch blog. | For a humorous take on the tech industry's shenanigans, subscribe to Robert X. Cringely's Notes from the Underground newsletter. ]

If you slept through your introductory CompSci courses, here's the short version. The P = NP question can be phrased in many ways, but the easiest visualization I've found is the subset sum problem. Say someone writes numbers -- integers, both positive and negative -- on sticky notes and sticks them on your desk. Can you find a bunch of sticky notes that sum to zero?

The subset sum problem is a classic example of an NP-complete problem: If somebody goes through all of the sticky notes on your desk, pulls out a bunch of them, and hands them to you, it's easy to see if the sticky notes sum to zero. Verifying the solution is easy. But finding the correct set of sticky notes can be very hard.

The P = NP problem, at first approximation, boils down to this: If you can verify the solution to a problem pretty quickly (in this case, add up all the integers and see if they total zero), can you also create a method for finding the solutions that runs pretty quickly (in this case, a method for finding zero-sum bunches that doesn't go exponential when you add more sticky notes)?

It's a classic problem -- many consider it to be the fundamental unsolved problem in computer science -- and it has a long history.

Some researchers trace the problem back to 1971, when Stephen Cook and Leonid Levin independently came up with a similar formalization. Dick Lipton, a P = NP expert from Georgia Tech, traces the problem back to a letter from Kurt Gödel to John von Neumann (both preeminent mathematicians) in 1956. So, depending on how you count, computer science folks have been puzzling over P = NP for 40 or 50 years.

Ten years ago, the Clay Mathematics Institute in Cambridge chose P = NP as one of seven Millenium Prize Problems and posted a $1 million bounty for its solution.

I remember when P = NP loomed large in academic circles many years ago. One of my thesis advisors told me that he figured some smart researcher would be able to prove or disprove P = NP, given a year off to try. Since then, hundreds -- probably thousands -- of sabbaticals have gone up in smoke trying to nail the devilish little equation.

Less than a year ago, the prestigious "Communications of the ACM" ran a cover article about the problem, with many leads but no definitive solutions, and hardly a glimmer of hope.

We haven't heard the last of this. It takes time to go through a 103-page proof, and many experts remain unconvinced. If you want to follow along, read Dick Lipton's blog and, for a second opinion, Scott Aaronson's blog.

Scott's a touch skeptical: "I really, really doubt that Deolalikar's proof will stand. And while I haven't studied his long, interesting paper and pinpointed the irreparable flaw, something deep inside me rebels against the charade of 'keeping an open mind,' when long experience with competent but ultimately unsuccessful proof attempts allows me to foresee perfectly well how things are going to play out here."

I figure this is the most exciting thing to happen in computer acience since Alan Turing nailed the halting problem.

This story, "Computer science breakthrough: The end of P = NP?," was originally published at Get the first word on important tech news with the InfoWorld Tech Watch blog.