## Monday, August 09, 2010 ... /////

### HP Labs researcher: P ≠ NP

The P versus NP problem is usually considered to be the most important open problem in computer science.

It is also one of the Millennium problems whose solver would receive USD 1 million from the Clay Institute (and who could reject it just like Grisha Perelman).

In essence, the problem is:

If "Yes" answers to a "Yes or No" question can be verified in polynomial time (NP), can the answers themselves also be computed in polynomial time (P)? Is P, which is known to be a subset of NP, a proper subset?
Vinay Deolalikar who also works in the HP Labs now claims to have solved the problem. His answer is that the two classes do not coincide: P is a proper subset of NP.

Here is his letter:
Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.

This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.

Comments and suggestions for improvements to the paper are highly welcomed.

Sincerely,
Vinay Deolalikar

Principal Research Scientist
HP Labs
www.hpl.hp.com/personal/Vinay_Deolalikar
Here is the 102-page-long paper, also in the original 66-page PDF form (also via Google Docs viewer).

So far, all the experts who have been asked gave this attempt the highest "apparent" rating they could but I find it unlikely that people can be "really sure" about a 102-page proof (which also depends on other things not shown in the paper) within 2 days.

Hat tip: Dr Paweł Gburzyński of Alberta Canada, Greg Baker (where you can read some more comments)

Possible mistakes

A few hours were enough for the readers to point out the first possible mistakes. A TRF reader mentioned the conflation of ordered and unordered characterizations. Here's a more detailed comment of this kind:

by David Mix Barrington
August 9, 2010 9:35 am

A potential problem that Lance pointed out to me: In Chapter 3 Deolalikar correctly quotes the Immerman-Vardi theorem as referring to finite ordered structures. But in Chapter 4 he quotes the Hanf and Gaifman theorems, which are true but much less interesting over ordered structures. Has Deolalikar just forgotten that his FO(LFP), because it includes FO, has the order and BIT predicates on elements of the universe? In that case every element is related by a tuple to every other element, and the “local neighborhoods” of those two theorems include every element in the structure. There have been other purported proofs of P != NP that have made this very mistake...

Disclaimer: I certainly haven’t understood how he uses these locality properties later, so I don’t know that he uses them incorrectly, but the disappearance of the ordered/unordered distinction in Chapter 4 is at least troubling.

J.S. Gate puts it in this way:

Scott Aaronson: your money is safe! Deolalikar has proved (if anything) that k-SAT cannot be characterized by a sentence in FO(LFP) over unordered structures:

“In our problem k-SAT, [the ordering] plays no further role. Specifically, the assignments to the variables that are computed by the LFP have nothing to do with their order.” (pg. 67).

Which is basically the same as saying that the structure is unordered; this does not rule out an LFP sentence that characterizes k-SAT by using features in the ordering relation.

Neil Immerman finds two flaws

There are two, possibly related, flaws that Neil Immerman, one of the world's experts on Finite Model Theory, found in Vinay's paper. See R.J. Lipton's blog (click) for details. You may find many other relevant articles about the P=NP topic on that blog, too.