Update on the Proof of P≠NP?

Thursday, 12 August 2010

The proposed proof that P≠NP raised more interest than expected. So how is it doing and what does it say about the whole process of science in the age of the wiki. We have an update.

The news (Proof of P≠NP?) that a proposed proof that P is not equal to NP released to the web earlier in the week has created more interest than one might imagine from such a dry academic problem. Of course if you understand what the significance of a proof that P≠NP then it isn't so dry or academic and issue.

Deolalikar2

Only a few days after the proof was made public early comments were collated in the well known (in computer science circles) blog Godel's Lost Letter and P=NP. The blog says it all but essentially there are objections to the proof - but in any new complex proof there will always be a lot of technical objections. The question is can these technical objects be reduced to something less harmful to the proof.

What is perhaps less well known about the actual process of mathematical proof is that it contains a proportion of social agreement as well as logic. A proof has to be accepted by mathematicans for it to achieve the status of a proof. Acceptance basically means that experts in the field can see that even if there are errors in the proof these can be fixed with a little work. Sometimes these small problems come back to kill the proof in later years when what appeared at first sight to be obvious proves to be intractable.

The blog documents the effort to work through the paper. The proof works by contradiction. It assumes that P=NP and then shows that this implies that there exists a polynomial time algorithm of a particular kind. Then the paper goes on to show that this leads to a contradition because of known statistical properties of random k-SAT instances for large k. k-SAT problems are about determining if a given Boolean formula can be made true by a suitable assignment of variables. Many of the objections to the paper focus on whether or not a contradiction has been achieved or if a "get out" clause been missed.

So far none of the objections have been a knockout blow to the proof and the author Vinay Deolalikar is standing by his work. A wiki has been set up to propose and process problems with the proof and Deolalikar is issuing updates to the paper on a regular basis.

Currently the feeling seems to be that the proof is not correct and cannot be corrected by minor tinkering, but it probably opens up a whole new route to tackling problems like NP=P and in time it could lead to a proof.

What is equally fascinating for computer scientists, and indeed all scientists is the way that the web has visibly changed the manner in which science is done. The open "outcry" vetting, discussion and general chewing over of this paper is quite unlike anything a scientist would have recognised as peer review only a few years ago.

It also representa a boost for computer science - a subject that has been falling out of favour with students, programmers and even academics in the past few years.

Further Reading