An view from some IBM theorists about the claimed proof that P does not equal NP

Ken Clarkson is one of the world experts on computational geometry. He is also a Senior Manager of Computer Science Principles and Methodologies at the IBM Almaden Research Center. Most impressive, in my opinion, he is one of Andy Yao’s Ph.D. students. Andy has had few students, relatively, and Ken is in an elite group.

Today I want to give a very short update on Vinay Deolalikar’s claimed proof of P${\neq}$NP.

A Presentation

Ron Fagin, Ken, and Ryan Williams gave a presentation recently at IBM Almaden on the claimed proof. It was an “IBMer’s Eyes Only” presentation. Ron has kindly released the presentation to the world—see this for the talk: video and slides. Here is where the link takes you to:

What’s all this about P not equaling NP?

Recently there was considerable interest in a proposed proof that P is not equal to NP. In response to that interest, some members of the theory group gave a talk to describe, for a general scientific audience, some aspects of this work and the community’s analysis of it. (The video starts a little bit into the talk; the speakers are Ken Clarkson, Ron Fagin, and Ryan Williams, in that order; the “D.” referred to is Vinay Deolalikar, the author of the proposed proof.)

Video of the talk (including all but the first few slides)

The slides

I have talked to Ryan about the presentation and he said it went well. There clearly is still great interest in the potential proof.

The Status of The “Proof”

As for the actual status of the Vinay’s “proof” I will add all I know, which is not much. Some is based on talking to people who do know and some on guess-work.

• Vinay recently gave a talk of his own at HP on his proof. The talk was very high level, and I understand that while interesting, it added little to the technical details.
• He is working on a “full” draft of the proof—it is getting much longer as all the details are added. Perhaps the “final” draft with be 200-300 pages in length.
• Finally, I have no idea if he will soon make the draft public, or if he has sent to to a journal. Or if he still plans to do that.

I suspect there are others who know much more, but that is all I know now.

Open Problems

A question that we are about to face is: how long should a claim of a great result remain unresolved? I think it is clearly in Vinay’s and the community’s interest to get the matter resolved soon. I still hope he is right, but I do hope that we get some closure soon.

September 15, 2010 8:42 am

I, for one, hope that P vs. NP remains open at least until I graduate.
I would be really disappointing if the biggest open question in my field were solved “too soon”.

September 15, 2010 8:52 am

The internet truly has given us an amazing tool for collaboration. It’s very exciting to see progress like this unfold, live, instead of through some sort of British Documentary film. Thanks for keeping us all updated.

September 15, 2010 9:16 am

Assuming that

a) The man is not a fool and

b) He has studied all of the “peer review” and had some discussions

Then the fact that he has not withdrawn the claim suggests that he still believes he has a proof.

(Some IBMers and presumably some HPers appear still to be at least keeping an open mind).

Out of respect for this risky strategy, we shall just have to wait and see.

September 15, 2010 9:44 am

Shouldn’t it be “A view”

5. September 15, 2010 10:30 am

Neil Immerman had a seminar talk at UMass yesterday on the claimed proof titled “P and NP in the Recent News”. (I don’t know if the slides or video are available–it’s probably irrelevant.) The relevant bit is that, according to NI, Deolalikar has sent his revised paper (which he claimed fixed the problems known at that time) to a journal for review.

September 15, 2010 11:47 am

RS,

Thanks did not know it was off to a journal.

• September 15, 2010 12:16 pm

I guess you meant to say that you didn’t know.

September 15, 2010 10:32 am

I, for one, hope that the question is NOT closed soon; a quick resolution is only really feasible if the proof is wrong. If the proof is correct (or can be fixed), it deserves years of scrutiny before it’s finally accepted.

We’ve been waiting 40 years already; what’s another 2?

September 15, 2010 12:21 pm

I would expect many years to gain confidence in the result, given its length. All it takes is one “without loss of generality” that doesn’t hold and the whole thing could fall apart. 200-300 pages is an awful lot of math in which such a fatal problem could hide.

A machine-checked proof, it should be noted, would give nearly instant acceptance of the proof, because only the definitions and the proof statement would need to be human-inspected. I shudder to think of how much manpower it would take to develop such a proof when the informal proof already takes 200+ pages, but it’s an intriguing idea for an important result.

8. September 15, 2010 5:43 pm

Just FYI, Vinay Deolalikar writes the status on his webpage:
” I have fixed all the issues that were raised about the preliminary version in a revised manuscript; clarified some concepts; and obtained simpler proofs of several claims. Once I hear back from the journal as part of due process, I will put up the final version on this website.”

9. September 15, 2010 10:43 pm

The video is great, thank you. I thought the SAT-Zero translation diagram was an especially nice touch.

September 16, 2010 1:28 am

This is a strange picture of Ken. It hardly resembles him. If you look closely, the left side is a mirror image of the right side…

11. September 16, 2010 1:59 pm

I’ve learned a lot from the Deolaliker episode … and hopefully this process is not over yet.

In particular, it led me to Oded Goldreich’s wonderful new book P, NP, and NP-Completeness, which has substantially (but no doubt incompletely) illuminated the definition of P for me.

For example, now I can frame dialogs like the following:

——————-

Alice: Hello Bob! Here’s an algorithm someone sent me in the mail … could you please decide whether it belongs to the class P or not?

Bob: I’m sorry Alice … membership in P is formally undecidable.

Alice: Gosh … no wonder separating P from NP is so hard!

——————-

How might this dialog be continued? I would be *very* interested in—and (hopefully) also instructed by—folks’ suggestions.

As an aside, the picture of Ken Clarkson is (by intent?) a thought-provoking example of what is called “bicameral portraiture“.

September 16, 2010 3:53 pm

I keep wondering why D would shy away from making his next drafts available for public review and send them only to a journal and select experts. That certainly doesn’t improve the acceptability (if any) of the proof; not even makes the process any easier. If I come up with such a proof (in a hypothesized-hypothesized ….-hypothesized world of course) I’d rather take advantage of the quickest, sharpest, and the most comprehensive review possible in the internet age. If I want the truth to be communicated, for the sake of the truth – that’s what I’d do. If am after the recognition, I’d do so even more. The sudden confidentiality —- I don’t get it.

September 19, 2010 2:07 am

Anonymous,

“I keep wondering why D would shy away from making his next drafts available for public review …”

I fully agree. He perhaps is looking for an official confirmation of the errors in his proof?

September 16, 2010 6:52 pm

As others have pointed out, the hardness of SAT can be captured in scenarios which do not involve complex solution spaces, suggesting that the hardness of SAT and the complexity of some SAT solution spaces are orthogonal notions.

So it would seem to follow that all attempts to resolve P vs NP with arguments about the complicated structure of certain SAT solution spaces are doomed to failure in ways that cannot be repaired. The tool being used simply cannot manipulate the object needing tinkering.

I notice that Vinay Deolalikar now states on his Webpage not that the proof has been sent out for “peer review,” but that it has been sent to a journal for “due process.” I wonder if he is now planning on publishing his masterpiece in one of the less academic periodicals.

I can’t imagine it passing real peer review now that it has been ripped to shreds by the online community.

September 16, 2010 10:23 pm

Please be accurate. The wiki page tracking community
review of the proof documents that the reference to
What’s new is that the tally “126 pages” has been removed.

September 16, 2010 11:41 pm

August 17th was after Deolalikar’s statement that “confirmations” had begun to roll in by August 8, and several days after the fatal error with the misapplication of finite model theory had been identified.

I do recall a statement by Deolalikar that he was planning on revising the paper to meet the points raised, and submitting it for peer review for publication in a journal.

Bear in mind that Claymath requires that proofs of the Millenium Problems be published in a peer reviewed journal and stand for two years.

The author has now removed all copies of his paper from the Web, leaving only a summary, and the current statement about “due process.”

I am simply curious about which periodical Deolalikar plans to publish in, and whether it is at the “Nature” or “Arxiv” end of the credibility spectrum.

September 16, 2010 8:09 pm

i am not a CS person. the way i understood it from the slides. SAT-0 has 0 as a solution. Constructing a sat0 problem itself involves the solution of a sat problem. and then if i am asked to solve this and not told that its a sat0 problem, i dont know that zero is a solution, so I have to search the entire space anyway. but the slides seem to imply sat0 is a very simple problem. i am sure i am not making any sense…any clarification will be appreciated.

September 16, 2010 8:43 pm

Hi, SAT0 is the following problem: “given a formula, is it satisfied by the all-zeroes assignment?” This problem is easily solved in polynomial time by simply setting all variables to zeroes and seeing what you get. However, the “solution space” of such a formula (the space of all possible solutions to the formula) can still be very complicated, similar to that of an arbitrary satisfiable formula. That’s all. It is just another way of saying that if you are trying to use the structure of solution spaces to argue that a problem isn’t in polynomial time, then your argument needs to be very very careful, because there are problems which have “complex” solution spaces but can be easily solved for a totally unrelated reason: all-zeroes just happens to be among their solutions.

September 16, 2010 9:53 pm

thanks…i am afraid still not completely clear to me. this problem: “given a formula, is it satisfied by the all-zeroes assignment?” is obviously in P, so is verifiability of a solution of any sat.
but for this above problem (within quotes), does speaking of space of all solutions make sense, its input is a formula not an assignment.. you can point me to a reference if i am being impossible.

September 16, 2010 10:36 pm

It makes sense to talk about the “set of satisfying assignments” of a formula, and also of a formula that happens to be satisfied by the all-zeroes assignment. That’s what a “solution space” is here.

Maybe you would like to read the wiki, which has more details on this and all the other points that were raised. There are some subtleties involved. Perhaps the fact that you’re confused means that you’re paying attention 🙂

The wiki is here: http://bit.ly/cBBzSa

September 16, 2010 11:08 pm

@ryan: now there is a paragraph in the wiki by someone starting with “The above arguments look like cheats. ” i dont understand any of that verifier stuff. but still think there is some kind of paradox going on. i understand the mapping, but you have to give me a sat0 formula and “also tell me it is a sat0 formula”, for it to become trivial. in stead if you translate to all-ones assignment, you have to tell me where you have translated it, for it to become trivial. its not enough to give me the formula and the input space of possible assignments.

September 16, 2010 11:45 pm

I think it’s cute that the all-zeroes assignment isn’t even guaranteed to be
in the solution space AT ALL for a formula in SAT0
(if your definition of solution space
is the same as mine). Proof: Choose a verifier V(X,f) which
given assignment X always answers NO if X is the all-zeroes assignment,
and for other values of X answers YES iff
the all-zeroes assignment satisfies f.

• September 17, 2010 11:37 am

I’m now confused too, but I think I’m confused about what Deolalikar is trying to do rather than about Ryan’s objection to it. What I don’t understand is that Deolalikar seems to be arguing that a particular instance of k-SAT has too complicated a structure to belong to P. I don’t see how that could work, even in principle.

A quick question. Suppose we were to do something simpler than what Ryan does (simple though that is) and just create a new problem, “Can we choose variables such that either f is satisfied or all variables are equal to zero?” This would have exactly the same solution space as f, except that the all-zeros assignment might have been added to it. Surely adding just one point to a solution space can’t change whether that solution space is simple or complex.

September 17, 2010 12:38 pm

could it be that deolalikar is not talking about the geometry but about the multivariate (probabilistic) distribution of solutions in that complex solution space (in rsb satisfiable phase) across random instances of k-sat all being in that phase. provided that sentence makes sense of course; my only knowledge of these terms is from ryans part of the talk.

September 17, 2010 12:41 pm

i meant “D is not talking about geometry of solutions for a single instance.”

September 17, 2010 2:21 pm

@confused: Yes, I am aware of the the sentence “The above arguments look like cheats” in the wiki. I wrote it! Note the mapping from SAT to SAT0 is not supposed to be polynomial time computable (and if P!=NP, it definitely isn’t).

@Tim: The argument was not for a particular instance of k-SAT, but for a subset of infinitely many k-SAT formulas. (For each number of variables n, one picks a randomly chosen formula according to the appropriate distribution.) Sorry if this wasn’t clear. I said “infinitely many” during the talk but I may have said it too quickly.

I think your modified problem would work equally well as a counterargument… but note our presentation was not close to a complete one. There were other subtle issues (such as that of “projections”) that we did not even touch upon in the talk (for good reason).

September 17, 2010 2:57 pm

Here is yet another way of mapping arbitrary SAT formulas into “easy” SAT formulas with essentially identical solution spaces, which I related to Ron Fagin back when the online discussion was still going on. I am posting it here in the hope that it will help clarify the earlier points.

For every satisfiable formula F with n variables, note there is some permutation Pi, and some integer k=0,…,n, under which the assignment

x_{Pi(1)}=0,…,x_{Pi(k)}=0,
x_{Pi(k+1)}=1,…,x_{Pi(n)}=1

is a satisfying assignment. (All the “zeroed” variables precede the “oned” variables.) Permute the indices of variables in F according to Pi, yielding formula F’. Now F’ is satisfied by at least one of the n+1 assignments

(x_1=1,x_2=1,…,x_n=1),
(x_1=0,x_2=1,…,x_n=1),
…,
(x_1=0,x_2=0,…,x_n=0).

We have mapped SAT into the problem: “given a formula, is it satisfied by one of the n+1 assignments (1,…,1), (0,1,…,1), …, (0,…,0)?”, which is polynomial time solvable. And we have done this by merely changing the variable ordering. The distances between solutions are preserved here as well, along with additional things like the number of variables set to 1.

• September 17, 2010 5:55 pm

I still struggle with this idea of how to exploit random k-SAT. Suppose we buy the idea that the hard instances of k-SAT occur at a particular critical probability, and would like to prove that (i) the hard instances have a particular very complicated structure that makes them hard and (ii) this is what distinguishes k-SAT from problems in P. To make that programme work we need to formulate some property that applies to problems in P. Or perhaps, thinking about it further, it is enough to formulate some property that applies hypothetically to k-SAT if we assume that k-SAT is in P. If so, then there are two ways I can imagine going. One is to say that we just use the randomness to find an instance with this special hard structure. So then the claim would be that no problem in P can have an instance that is hard in that way — a claim that is trivially false. Another is that it cannot be the case that almost all instances, chosen with this distribution, have the hard structure. In other words, the distribution would be involved in a very important way. But how could we hope to show that that would not apply if the problem is in P (ignoring the fact that we can’t hope to prove it because we can find a problem in P with instances that have more or less the same solution spaces)?

More generally, it seems utterly obvious that this “pointwise” approach (look at the structure of the solution spaces of specific instances) has absolutely no hope of succeeding, and that what is needed is an examination of the structure of the set of satisfiable formulae, or possibly the entire ensemble of solution spaces, considered as a sort of “moduli space” of structures indexed in an interesting way. Of course, if we try that then we soon run into familiar barriers …

September 17, 2010 7:06 pm

I agree, I have no idea how to exploit properties of random k-SAT to prove unconditional lower bounds. Maybe a more promising approach would be to look at formulas at the satisfiability threshold, and argue somehow that it’s hard to distinguish the satisfiable ones from the unsatisfiable ones here, whp. Of course such an argument would not speak of the structure of solution spaces.

However, it feels weird to try even this: whp a random formula has additional structure that an algorithm might be able to exploit, so separating P and NP in this way would only be harder to do. (In fact this structure has been exploited to prove that some problems are hard to approximate. That is, some inapproximability results can be proved assuming random 3-SAT is hard for P, but are not known to be hard assuming P != NP. One reference is Feige’s “Relations between average case complexity and approximation complexity”, STOC’02.)

September 18, 2010 7:31 pm

the proof may very well be dead, but after reading parts of the MS again, I am trying to see whether these trivial objections about geometry kill the proof. as far as i can tell, the only fact about geometry that has been used in the MS is that there are exponentially many clusters of solutions in the hard phase and hence we can get a distribution by generating plenty of solutions, starting with different partial assignments. so this gives a multivariate mixture distribution (mixture being due to clusters), that is parametrizable by a different number of parameters depending on whether k-sat is in P. From the wiki, Ryan’s objection for partial assignments is “So for every instance of “k-SAT-Partial-Assignment” we can find an instance of “SAT0-Partial-Assignment” (which is again a trivial problem) with the same solution space structure.” Tao in his projecton wiki has defined partial assignment as an assignment of initial variables (x1,…xi). if this is the definition then the above objection looks valid. but on page 69 of the MS at
http://peopleyun.com/wp-content/uploads/2010/08/pnp_8_11.pdf , I found this definition: To get a formal deﬁnition, ﬁrst we deﬁne a partial assignment of a set of variables (x1 , . . . , xn ) as an assignment of each variable to a value in {0, 1, ∗} . Are these definitions equivalent ? How is the sat0 objection modified if the initial assignment is in a random order ?

September 18, 2010 10:52 pm

I agree with Confused. To me the SAT0 argument simply implies that every “hard” instance of an NP-complete problem can by solved by a polynomial-time algorithm – which is unsurprising (and if you always knew how to pick the right algorithm, then P=NP.)

So the question to me is how many such algorithms does one have to try before finding one that solves a given instance of an NP-hard problem? After all, it’s not necessary to show that every instance of an NP-hard problem requires a non-polynomial time solution (in fact, I believe that the vast majority of NP-hard problem instances can be solved in polynomial time – so “most of” NP is in P).

Here’s an approach to the P vs NP question that I came up with. Imagine using a “meta-algorithm” to solve an instance of an NP-hard problem. A meta-algorithm is one that simply tries a series of different polynomial-time algorithms until it finds one that solves this particular instance. Now, sometimes we will “luck out” and solve the problem quickly (as in the SAT0 example). However this particular meta-algorithm will not be able to solve every instance so quickly – in fact, some instances will require our particular “meta-algorithm” to test an exponential number of algorithms – until it finds one that works.

Clearly, we can choose only one meta-algorithm to solve our problem (and still solve it in polynomial time). And as long as there is nothing in this particular instance that tells us how best to order our algorithms, then P≠NP.

• September 19, 2010 11:12 am

May be but does this really matter?

October 2, 2010 1:09 am

Hi, I too am trying to understand the SAT0 argument. Probably it is too late to expect a reply to this but here goes:

> SAT0 is the following problem: “given a formula, is it satisfied by the all-zeroes assignment?”

I was wondering: why doesn’t the solution space to SAT0 involve just two “points”? One is the all zeros assignment, the other is everything else. It seems odd to say that the solution space to SAT0 consists of all 2^n assignments of n variables.

> We have mapped SAT into the problem: “given a formula, is it satisfied by one of the n+1 assignments (1,…,1), (0,1,…,1), …, (0,…,0)?”

Again, the solution space seems much smaller than 2^n, so to say it is just as complex as the full k-SAT solution space does not make sense to me.

Clearly I am missing something – probably a rigorous definition of solution space would resolve the issue.

September 16, 2010 8:11 pm

Hi,

Thank you Professor Lipton for such a great blog!

With respect to Vinay Deolalikar’s claimed proof, I must say that I am still very intrigued by it. Whatever anyone says, he brought together such novel ideas to give a very interesting proof strategy.

I think it was said that the P NP problem is like a sheer cliff where no one knows how to even get a foothold. For him to get so close to a proof is really remarkable, and that too outside of academia. I believe he should be given more time by the community before stamping his ideas as fatal.

I am not sure why exactly every flaw that is brought up is described as fatal. Have others proved that his general strategy can not be made correct? According to his website he has managed to fix the issues that were raised. Such a person who could come up with such original work, may also be able to fix it. I would personally love it if he again posted his work for all to see. But we must realize that his work was leaked and perhaps he wanted journal and not internet review of his work.

I think he is probably one of the biggest underdogs I have heard of in a very long time. Everyone is out to perform a top kill on his work.

Even if his work doesn’t go the distance, I salute him on his brave attempt! Let’s all have patience.

September 16, 2010 8:34 pm

It’s extremely inaccurate to say that “everyone is out to perform a top kill on his work”. Most of us who convened on Lipton’s blog to talk about the paper were not here to slam anyone. We honestly wanted to understand what was going on in the paper, and figure out if it had a chance of working. After having spent that time (and collectively, everyone generated over a thousand blog comments), we made our conclusions. Some of us were grumpy during the process, but you’d be too if you actually tried to read the paper and got as confused as we did.

Don’t get me wrong: I am not making a subtle jab at Lance or Scott or Bill or anyone else who stopped reading after the first few pages. Those guys are all friends of mine, and are free to spend their time however they like (especially when they’re on vacation). If you don’t care for their opinions then don’t read their blogs.

Now back to real work…

September 19, 2010 2:14 am

I would call D’s claimed proof episode more of a “The Comedy of Errors”. Besides it is due to the majority’s frenzy that NP !=P.

September 20, 2010 12:21 pm

Thank you for this comment W.Howell, I think you speak for a lot of us!

It is too bad that Deolalikar has had to put up with a lot of this OVER scrutiny. It is understandable to review his work with interest and skepticism even. But here is someone making an honest research effort and he should be respected.

What really is terrible are the attacks made which are personal in nature. From his country of origin, age, place of employment, etc. The lowest blow I saw was someone mocking his dedication to his DECEASED parents, and this too coming from those at the top in academia. It really gives the community a bad name.

I support Deolalikar and hope that he is able to come up with more new and refreshing work!

September 17, 2010 10:26 am

Best Case Scenario: The proof is correct and understandable. I hope this is the case since then the problem is SOLVED and we could all ENJOY the solution.

Middle Case Scenario: The proof is correct but very hard to understand. At least it would be SOLVED but most of us could not enjoy it. (FLT was like this.)

Worst Case Scenario: The proof is incorrect but its very hard to find the mistake and this takes years of time and effort. Actually even this would not be bad if that effort leads to interesting results.

Okay Scenario: The proof is incorrect and this is found out rather quickly. While P NP would stay unsolved at least the current proofs status would be resolved.

• September 17, 2010 3:41 pm

I admire the above post *very* much … four plausible outcomes … all pretty good. Moreover, two negative outcomes did *not* happen: (1) no-one cared enough to work on the problem, and/or (2) no-one much cared about the results.

It is a non-trivially good thing (IMHO) that neither of these happened.

September 19, 2010 2:21 am

Bill,
So you all are (again) making a tacit assumption that NP !=P. (as per you last poll)

What if NP == P? What then he (or anyone else) would be trying to fix?

17. September 17, 2010 12:59 pm

I would like to really have “the Best Case Scenario” of W. Gasarch:
The proof is correct and understandable by every specialist in this field.
It will be fantastic.
best,
Dr. Kathrine M. (Switzerland).

18. September 18, 2010 9:32 am

How long should a claim of a great result remain unresolved?
I think Vinay Deolalikar is lucky. He has already a road map to fix his proof. Someone may say that the proof is unfixable but he claim that “I can fix it” so we have to wait. The worst case for a claim of a great result is the case where no gap, no counter-example have been found and still suspecting something wrong in the proof.

• September 18, 2010 10:48 am

I’m not sure I understand the word “fix” in this context. The situation, as it appears to me (and by no means just to me), is not that he has a proof with one or two bugs in it, but that he doesn’t have a proof at all. To follow Terence Tao’s example by giving a car analogy, “fixing” the argument would be a bit like “fixing” a car when all you actually had was some bodywork. That’s not fixing it — it’s making it. Thus, even if Deolalikar now comes up with a correct proof, it still won’t show that his first proof was basically correct.

• September 18, 2010 2:11 pm

So your conclusion is that Deolalikar’s case is closed and there is no reason to wait the revised version unless he provides a completely different second proof.

September 18, 2010 3:10 pm

For the revised proof to be correct, it will have to employ an entirely different methodology than the current proof.

The objections to the current proof demonstrate an entire class of arguments which cannot be used to decide P vs NP, of which the current proof is a single instance.

So absent a miracle, the proof has fallen and it can’t get up.

September 18, 2010 6:31 pm

Lance Fortnow had a post a while back about the lifecycle of some P vs NP proofs:

http://blog.computationalcomplexity.org/2009/01/so-you-think-you-settled-p-verus-np.html

September 19, 2010 2:29 am

Lance continues to be a witness to “the history repeats itself”.

September 19, 2010 11:34 am

Thank you so much for such a stimulating blog!!

Although this is by no means clear from the manuscript, it seems that Deolalikar’s strategy has not so much to do with the “pointwise” structure of the solution space, but with how the purported P-algorithm explores it. Perhaps what he really wants to show is that such an algorithm must be “continuous” in the sense that, if the algorithm produces a different answer after flipping one bit, the input points must still be “far” with respect to the polylog-parametrization. The clustering phase would then supposedly rip this topology apart.

Unfortunately, no public version of the paper makes a falsifiable statement in this critical part of the proof… 😦