P=NP Update

As we reported here, there was much flurry on the internet about a potential proof of the P=NP problem.  There is still an ongoing discussion about the proof and the ideas introduced in the proof, but the consensus seems to be that there is some serious doubt that the current paper settles the question.  As Terence Tao put it:

I think there are several levels to the basic question “Is the proof correct?”:

1. Does Deolalikar’s proof, after only minor changes, give a proof that P != NP?

2. Does Deolalikar’s proof, after major changes, give a proof that P != NP?

3. Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No” (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added”. But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days).

— Terence Tao

But we’ll keep you posted on any big new developments!