Wednesday, September 22, 2010

Wednesday Math, Vol. 128: Maybe N = NP after all...

A few episodes back in Wednesday Math, I reported on a soon to be published proof that was supposed to answer once and for all whether the problems in the set P had any overlap with the seemingly tougher problems in the set NP. Vinay Deolalaikar said he had proved they had no overlap, but his proof was found to have a few glitches in it.

I hope he didn't start spending the million dollar prize he would have pocketed if his work had been right, because that would be embarrassing.

The search continues.


ken said...

The proof may be bad, but you shouldn't count on P being equal to NP. As I mentioned in the email a while back, I'll be disappointed if this proof is bad, but I'll be stunned if P==NP.

I've read enough of the "proof" to be fascinated at the threads he's woven together. Particularly the relationship between computational complexity and locality.

Matty Boy said...

Good point. It's like the Riemann Hypothesis. No one's proved it true or false, but the smart money is that it's true. Likewise, most people are going with the idea that P and NP separate.