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

[gkhouston]

1. Gawd, but I hated the P and NP stuff. Glad that shit's behind me.

Interesting that someone's come up with the proof, though.

[qb]

2. This explanation is one I can almost understand...

but how does a solution improve computer programming?

[gkhouston]

4. IIRC, in the past, once you'd proven a problem was NP-complete, you pretty

much gave up hope of finding a polynomial time algorithm to solve it. I'm thinking this says if you show the problem is inherently NP, you're not going to find a polynomial time algorithm. Sort of a negative result, but still good to know.

[qb]

6. Thanks. After a little more reading about polynomial time algorithms I'm starting to get it.

[unblock]

9. you mean if the problem is np-complete, you're not going to find a polynomial time algorithm.

rather than "inherently np" -- all "p" problems are also "np" problems.

[gkhouston]

11. Yes, sorry. n/t

[midnight]

3. This reads like a blur to me, but I'm glad that there are

people like you to move us forward.

[BootinUp]

5. Seems there are a lot of skeptics

at this point about the proof, from a quick scan of the various blogs/wiki on it.

[gkhouston]

7. There's no surprise. I know one married couple, both computer scientists,

who thought their oldest child's first sentence was going to be, "You're wrong!! And I can prove it!"

[unblock]

8. i've seen MANY attempted proofs of this, so i'm not buying into it just yet

though nearly everyone in this area seems convinced that p != np, the proof has always been elusive.

[Renew Deal]

10. You never know what's going to interest DUers.

I posted it because I thought some of the math nerds would be fascinated. It made it to the greatest page. Who would have thought?

[unblock]

12. at least 5 math nerds :)

and the unrec crew doesn't see the politics in it :evilgrin:

[Lucky Luciano]

13. This problem has a $1mm bounty on it from the Clay Institute.

The CLay Institute had a bounty on 7 problems of a million bucks. One, the Piincare conjecture in dimension three was solved by a reclusive weirdo named Grigory Perleman who turned down the prize so that he could continue living with his mother in a cockroach infested apartment in Moscow. Piincare conjecture was a tough one - took over 100 years. In dimensions 5 and higher was much easier to prove - dim 4 was very hard, but solved some time back. Perleman also rejected the Fields medal for his work. I did a lot of work in topology so piincare was of interest to me. P-NP was less interesting to me, but its solution would be a BIG deal.

Lots of typos - not gonna fix them. Hard typing on iPhones.

[slutticus]

14. Some good links here:

http://www.ugcs.caltech.edu/~stansife/pnp.html

http://michaelnielsen.org/polymath1/index.php?title=Deolalikar_P_vs_NP_paper

[IDemo]

15. I'm familiar with NPN and PNP devices. Not so much on this, though