Deolalikar Responds To Issues About His P≠NP Proof
A principle for checking proofs with an application to the proof
Vinay Deolalikar is standing by his claim and proof. He and I have been exchanging e-mails, and as noted in the several comments, he has updated his paper several times. The updates are trying to answer some of the questions raised here and elsewhere. However, the consensus seems to be best summarized by a recent comment here by Terence Tao:
I think there are several levels to the basic question “Is the proof correct?”:
- Does Deolalikar’s proof, after only minor changes, give a proof that P NP?
- Does Deolalikar’s proof, after major changes, give a proof that P NP?
- Does the general proof strategy of Deolalikar (exploiting independence properties in random -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.)
Today I wish to talk about something other than the PNP proof. But it is hard to get back to other issues right now. I do agree with Tao that we need to move on to other topics, and let the proof checking continue at a more relaxed pace.
I would like to share a proof searching trick that I have always used; it must be well known, but I do not know a name for it. The method is quite relevant to the emerging biggest issue in the correctness of Vinay’s proof.
Suppose that Alice is trying to prove , some statement that Bob is interested in seeing proved. Alice is working hard trying to understand the problem: she reads the known literature, she talks to experts, she tries some examples, and she thinks hard about the problem.
Finally, after months of hard work, Alice has an outline of a proof. She has not checked all the details, but she is quite excited about the potential. She thinks she has her proof. Imagine that she is about to go to explain the proof to Bob.
Just before she does this, Alice notices the following. Let’s call her proof of the statement . She notices that the same proof—perhaps slightly changed—will also prove . In a sense she sees that
where is a slight variation of her proof .
Here is the principle: this is bad, very bad, if is known to be false. Even if is an open problem, then this could be an issue. The reason is Alice felt she had a nice proof , but did not think her method was powerful enough to solve the hard open problem .
I use this principle—unfortunately all too often—to shoot down my own proof attempts. More than I care to admit, I find a clever “proof” of something, but then realize by the principle it will prove too much. It will either prove something dead-wrong or something that is way too hard for my weak method.
Here are two simple examples of this principle: one imaginary and one real.
Suppose Alice is working on the Riemann Hypothesis. This famous problem says that all the non-trivial zeroes of the zeta function must lie on the line . The zeta function has so called trivial zeroes at
She proves that all the non-trivial zeroes of the zeta function must have a left-to-right symmetry about the line . She then uses this cool lemma to solve the Riemann Hypothesis. She is overjoyed. But after checking her argument she discovers that her cool lemma never used the fact that the zeroes were non-trivial. Clearly, this is a problem, since it would imply that the zeta function has zeroes with real part greater than . This is false and so her lemma has to be re-thought
I have worked on a much less important problem, but one where the principle played a role. I had an idea for proving a certain complexity theorem—nothing like PNP—but still an open problem. I had discovered a partial result based on a “trick” that I had discovered. I was pretty excited and quickly thought I could generalize my trick to solve the full problem. Alas, I saw that the principle applied here: if I could do what I planned, then my proof would yield a result that would violate a known complexity theorem. The problem I worked on is still open. Oh well.
The Proof and The Principle
A number of researchers—including Avi Wigderson and Ryan Williams—have pointed out that Vinay’s proof could fall to the above principle. They do not state their concern in this way, but it is essentially a potential violation of the principle.
In particular their concern is how does the proof tell -SAT from -SAT? If Vinay’s “proof” would work as well on both these types of SAT problems, then there is a fundamental difficulty. Of course, -SAT is long known to be in polynomial time, so if his proof does not have a critical step, lemma, or place where is used in an essential way, then it has problems.
I still do not know for sure what to conclude about this. But this issue is definitely one of the biggest ones that we have seen raised. It is not sufficient to rely on some results having been proved for or —the proof must show how this restriction is used in an essential manner. This may require ensuring that the proof strategy can’t be adapted to properties expressible in the same terms, which would prove an known to be false.
There is a longer discussion of this and related issues with his proof at the wiki page.
Vinay has just responded directly to a number of us in an attempt to explain how his work does use . It is still a bit early to see if his explanation is sufficient, but he does state some technical differences between -SAT and -SAT that he claims to exploit. I have communicated directly with him to ask that he would allow his comments to be made available to the community. He has agreed. (I made slight edits to make the formulas compile into LaTeX.)
Let me try to answer the question, which is “Why does my proof fail for 2-SAT, known to be in P.” The proof requires that the solution space of the CSP be “sufficiently hard to describe.” By that we mean, not possible to describe with fewer than independent parameters. XORSAT does not violate this since its linearity allows simple specification. 2-SAT does not violate this since it does not enter the d1RSB phase. In contrast, 9-SAT onwards do enter the d1RSB phase, and in the absence of properties such as linearity, it is not possible to specify the joint distribution of the covariates in this phase with independent parameters. However, both range and value limited interaction models that underlie LFP algorithms can only furnish such independent parameters to describe their solution spaces. Hence the contradiction. I think this is really the major point. There are many details in the various chapters. I wrote Chapter 3 yesterday to discuss some of this. I discuss the significance of the poly quantity etc.
Of course the key questions remain: Is the proof correct? Or can it be fixed?
Perhaps the last question is what did we learn from the last few hectic days. I think I learned three things: First, that the community is extremely interested in our basic question, P=NP? I find this very positive. I was shocked at the tremendous interest that was generated.
Second, I like that the community reacted in a mostly positive and supportive manner. I think we owe Vinay a thanks, no matter what the final outcome is. He has raised some interesting connections that, as Tao says, may be useful in the future. He also showed how people can ask hard questions, and how the community can be helpful. Yes, there were some tough comments here and elsewhere, but for the most part I think the experience has been positive.
Finally, I realized that it is not possible to keep up the hectic pace of the last few days for much longer. I hope we helped, I hope we were always positive, and I hope the work here in trying to resolve this exciting event has been a positive contribution. I thank you all for your kind interest.