Computer science breakthrough: The end of P = NP?

[Renew Deal]

Researchers claim that one of the great unresolved mathematical questions in theoretical computer science just bit the dust
By Woody Leonhard | InfoWorld

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.

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)?
<snip>

http://www.infoworld.com/t/code-analysis/computer-science-breakthrough-the-end-p-np-583

You can read the paper here: http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf