Putting my money where my mouth isn’t
A few days ago, Vinay Deolalikar of HP Labs started circulating a claimed proof of P≠NP. As anyone could predict, the alleged proof has already been Slashdotted (see also Lipton’s blog and Bacon’s blog), and my own inbox has been filling up faster than the Gulf of Mexico.
Alas, a simple “top kill” seems unlikely to work here. What’s obvious from even a superficial reading is that Deolalikar’s manuscript is well-written, and that it discusses the history, background, and difficulties of the P vs. NP question in a competent way. More importantly (and in contrast to 98% of claimed P≠NP proofs), even if this attempt fails, it seems to introduce some thought-provoking new ideas, particularly a connection between statistical physics and the first-order logic characterization of NP. I’ll leave it to the commenters to debate whether Deolalikar’s paper exhibits one or more of the Ten Signs A Claimed Mathematical Breakthrough Is Wrong.
“But enough question-dodging!” you exclaim. “Is the proof right or isn’t it? C’mon, it’s been like three hours since you first saw it—what’s taking you so long?” Well, somehow, I haven’t yet found the opportunity to study this 103-page manuscript in detail. Furthermore, I don’t plan to interrupt my vacation time in Israel and Greece to do so, unless experts who have studied the paper in detail start telling me that I should.
Unfortunately, I can already foresee that the above response will fail to staunch the flow of emails. As a blogger, I’m apparently expected to
(1) render an instantaneous opinion on any claimed mathematical breakthrough,
(2) be consistently right, and
(3) do the above without looking like I’m being unfair or rushing to judgment.
While requirements (1) and (2) are not so hard to satisfy simultaneously, (3) makes my job an extremely difficult one. In fact, I could think of only one mechanism to communicate my hunch about Deolalikar’s paper in a way that everyone would agree is (more than) fair to him, without having to invest the hard work to back my hunch up. And thus I hereby announce the following offer:
If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.
I’m dead serious—and I can afford it about as well as you’d think I can.
Update (August 10): One whole day into this saga, Dick Lipton and Ken Regan have written a detailed post setting out four possible problems that have already been identified in the proof, and which the ball is now in Deolalikar’s court to address. Kudos to Dick, Ken, and numerous commenters for actually digging into the paper (unlike some lazier folks I could name 🙂 ).
Another Update: Since some journalists seem (unbelievably) to have missed the point of this post, let me now state the point as clearly as I can. The point is this: I really, really doubt that Deolalikar’s proof will stand. And while I haven’t studied his long, interesting paper in detail and pinpointed the irreparable flaw, something deep inside me rebels against the charade of “keeping an open mind,” when long experience with competent but ultimately unsuccessful proof attempts allows me to foresee perfectly well how things are going to play out here. I would make a terrible trial court judge: ten minutes into the proceedings, I’d be screaming, “The defendant obviously did it! I sentence him to death!” Fortunately I’m not a judge, and I have a way of stating my prediction that no reasonable person could hold against me: I’ve literally bet my house on it.
Yet Another Update: What’s emerged as the perhaps central issue is the bane of so many attempted P≠NP proofs in the past: namely, why does the proof not work for 2SAT, XOR-SAT, and other problems that are very similar to 3SAT in their statistical properties, yet for which polynomial-time algorithms are known? If Deolalikar can’t provide a clear and convincing answer to that question, the proof is toast.
Follow
Comment #1 August 9th, 2010 at 3:00 am
If you can’t afford 200k, then why not make the vow for 1 Mee-yillion dollars? If you feel 1000k is silly, then why isn’t 200k equally silly?
—-
Might as well create a prediction for this; I assume 5 years ought to be enough time for the proof, if correct, to be verified & accepted, or to be refuted.
http://predictionbook.com/predictions/1588
Comment #2 August 9th, 2010 at 3:06 am
gwern, the flaw in your argument is that “being able to afford something” is not a binary proposition. I can afford $200k, but not in the same way Bill Gates can afford $200k.
Comment #3 August 9th, 2010 at 3:13 am
Thanks for writing this so I can forward it to people. I’ll certainly need it less than you though. 🙂
Comment #4 August 9th, 2010 at 3:28 am
Wow, alright then. I guess it’s either almost certainly wrong or Scott Aaronson is quite off his rocker.
No expiration date on that, Scott? Like you’re pretty sure it doesn’t even provide a fruitful direction? (Because if it did it seems there would be too much risk of Deolalikar eventually winning for you to be willing to make a bet like that.)
Side note: We can compute Scott’s probability of the proof’s correctness if we make an assumption about the value to him of conveying his certainty to us. Let’s say that’s $100. Then Scott thinks there’s a 0.05% chance the proof is right (or fixable).
Comment #5 August 9th, 2010 at 3:39 am
Daniel: If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it.
Comment #6 August 9th, 2010 at 3:44 am
Daniel, there is also a side benefit to increasing the prize amount, namely, that we should like someone who proves P != NP to receive a lot more than $1M worth of prestige.
My own probability that Deolalikar will claim the millenium prize has been updated to 10%.
Comment #7 August 9th, 2010 at 3:59 am
“Alas, a simple “top kill” seems unlikely to work here.”
Scott, would it be possible for you to comment on how this potential proof escapes the Baker, Gill, and Solovay restriction that any proof for P != NP cannot relativize?
I don’t mean any disrespect to Vinay Deolalikar, I’m just having trouble understanding this point.
Comment #8 August 9th, 2010 at 4:01 am
Scott: But I don’t see how it changes your utility for $200k very drastically. (If it were an alleged proof of P=NP that would be another story.)
Liron points out that some fraction of the $200k you would gladly contribute to Deolalikar out of genuine gratitude or somesuch emotion. But I would think that would be a small fraction.
So the implication of your bet still seems to be that you think there’s only a fraction of a percent chance that Deolalikar has a proof.
Comment #9 August 9th, 2010 at 4:22 am
Richard: The paper is all about the local properties of a specific NP-complete problem (k-SAT), and for that reason, I don’t think relativization is relevant. Personally, I’m more interested in why the argument makes essential use of uniformity (which is apparently why it’s supposed to avoid Razborov-Rudich).
Comment #10 August 9th, 2010 at 4:25 am
So the implication of your bet still seems to be that you think there’s only a fraction of a percent chance that Deolalikar has a proof.
If I were a Bayesian rationalist, I’m sure I’d agree with you!
Comment #11 August 9th, 2010 at 4:33 am
I would be very amused if Deolalikar’s proof is wrong, but that he still gets awarded the prize because it leads to insights that give a proof that P=NP
Comment #12 August 9th, 2010 at 4:42 am
“insights that give a proof that P=NP“? Interesting 🙂
Comment #13 August 9th, 2010 at 4:42 am
If I were a Bayesian rationalist, I’m sure I’d agree with you!
Ha, yes, hence my original “or Scott is off his rocker” caveat. 🙂
Anyway, maybe “you highly doubt the proof will hold up” is the most we can say.
I love that you did this, by the way. It makes your take on this so much more informative than others with equal expertise! (Unless of course I’m wrong above in which case I can’t fathom your thinking on this.)
Comment #14 August 9th, 2010 at 4:53 am
Scott: I, for one, would be interested to know how a possible proof of P != NP would change the life of a theoretical computer scientist.
PS: I was under the impression that this was, more or less, the `expected’ answer.
Comment #15 August 9th, 2010 at 5:08 am
KK: P≠NP is exactly the ‘expected’ answer! But proving that expected answer has been the central goal of the field for 40 years—not so much (in my opinion) because the answer itself is in serious doubt, as because of how much will need to be learned about computation on the way to the proof. If P≠NP is proved, then to whatever extent theoretical computer science continues to exist at all, it will have a very different character.
Comment #16 August 9th, 2010 at 5:47 am
So, if you don’t mind me rephrasing what you said to see if I understand correctly: It’s not that the answer itself will provoke a dramatic change to the field (as opposed to a proof of P==NP). It’s that a proof would require paradigm-shifting insights about computation, and investigation of these new insights will become the main subject of theoretical CS.
BTW, I live in Greece (not sure if you ever been here before), so If you want any specific pointers please let me know.
Comment #17 August 9th, 2010 at 8:25 am
I still don’t see why the proof would dramatically change your life. Would you mind expanding on that more?
Comment #18 August 9th, 2010 at 8:53 am
@Greg: If P were to equal NP, a lot of results in theoretical computer science would become very uninteresting. I am amused how losing $200,000 would be the least of the changes to Scott’s life, though.
Comment #19 August 9th, 2010 at 8:59 am
Finally a good provocative posting again :-). Keep up the good work!
Comment #20 August 9th, 2010 at 9:19 am
@coherentsheaf: Do you mean if P were not equal to NP? So his life would get boring if P!=NP is proven?
Comment #21 August 9th, 2010 at 9:20 am
Scott will lose a substantial amount if he is wrong, but would win almost nothing (what is the value of 15min of blogger fame?) if he is right.
So whatever his probabilities, and independent of him being a Bayesian or not, this ‘bet’ is irrational unless he is *very* sure about this.
Comment #22 August 9th, 2010 at 9:23 am
The Kleene-Rosser paradox is a counter-example to the Immermann-Vardi theorem. It is in P and not in FOL+LFP.
This is sufficient.
Comment #23 August 9th, 2010 at 9:29 am
We don’t know what side bets Scott has going with other people about P≠NP. Perhaps he stands to win more than $200k if Vinay Deolalikar wins the Clay Millennium Prize.
Comment #24 August 9th, 2010 at 10:00 am
@davinci: You are absolutely right. Disclosing only one leg of a multi-leg financial transaction/bet would explain Scott’s behavior (but it would also be dishonest).
There is one more possibility.
1) Scott has his own proof ready .
2) He does not want to share the prize money.
3) He uses this blog post to draw more attention to this claimed proof so that there is a higher chance that somebody finds a flaw.
Comment #25 August 9th, 2010 at 10:12 am
davinci and wolfgang: You’re getting warmer! But my true motivations were far more devious still: I wanted to stop having to answer emails about this. To me, that’s easily worth the possibility of paying $200k.
Comment #26 August 9th, 2010 at 10:27 am
Has this actually substantially reduced the number of emails you are getting?
Comment #27 August 9th, 2010 at 10:28 am
scott. you are a true Internet Superheroe!
Comment #28 August 9th, 2010 at 10:50 am
Scott: 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.
Comment #29 August 9th, 2010 at 11:08 am
Would the “proof” extend to the quantum realm?
Comment #30 August 9th, 2010 at 11:10 am
Davinci, side bets do not give Scott motivation for a unilateral $200K offer unless that offer is an explicit term of the other bets. Which would be unusual.
However, if Scott were a bayesian rationalist, he’d probably be able to easily make $200K by dutch-booking everybody else in the complexity theory scene.
Comment #31 August 9th, 2010 at 11:12 am
Fernando: Kind of a premature question, don’t you think? 🙂 But no, I don’t see any reason why it would.
Comment #32 August 9th, 2010 at 11:14 am
I still don’t see what the big deal with proving P!=NP is. This is the assumption we’ve been working under for decades anyway, right? Can anyone enlighten me?
Comment #33 August 9th, 2010 at 11:19 am
LOL … there is another possibility that is entirely consistent with Scott’s Feynman-style “trickster” persona. Namely, that Vinay Deolalikar’s article won’t win the Clay Millennium Prize even if is correct.
How might this be? Easy … if there is a prior proof that is circulating (quietly) … and Scott (or folks he trusts) have reviewed this “Proof B” … with the result that Proof B is already scheduled for publication “in a refereed mathematics publication of worldwide repute” (per the Millennium Prize Rules).
Now, do I myself believe this theory? Definitely not! Given that both Scott and Feynman are much trickier than me, the only thing I’m sure of is that the full story of Scott’s proposition bet (as such bets are called) will be lots of fun when it is revealed.
Some of Feynman’s jocular tricks have taken decades to pay-off, and I’m confident that Scott is similarly patient. For example, only nowadays do we recognize that Feynman’s 1961 textbook Quantum Electrodynamics has no field operators in it … no bra-ket vectors … no density matrices … no mention of any linear Hilbert space at all. That was one-in-the-eye for the Hilbert-space quantum axioms of Dirac, Schwinger, Tomonaga, and Dyson … and the full import of Feynman’s trick is still sinking-in today, after almost fifty years. Now *that’s* master-level jokery! … the kind of jokery that makes every aspect of math, science, and engineering far more fun … and is precious for that reason.
Comment #34 August 9th, 2010 at 11:35 am
This is a nasty post, and since Scott made the point that being nasty is his duty as a blogger rather than his “natural” tendency, it also sheds a bad light on the nature of scientific blogging. (The 200K business, makes the post nastier.)
Comment #35 August 9th, 2010 at 11:36 am
Steve, one doesn’t need to be a Bayesian rationalist to win with dutch booking. You just need to crunch the numbers for that. It doesn’t require you to estimate a probability. Actually, I doubt that in practice one could make that much money from it because people are rarely willing to bet much money on these sorts of questions.
Comment #36 August 9th, 2010 at 11:38 am
@Greg. Yep, note that the tagline for Shtetl-Optimized would become false if P=NP. I think it was on Lance Fortnow’s blog where it was said that theoretical computer scientists have essentially bet their (academic) lives on P!=NP.
Comment #37 August 9th, 2010 at 11:52 am
Gil: I just can’t win, can I? How could I have conveyed my honest opinion in a way that you wouldn’t consider “nasty”?
Comment #38 August 9th, 2010 at 11:59 am
Students in particular might benefit from reading Lance Fortnow’s terrific review The status of the P versus NP problem (available on-line).
Lance’s review says in its conclusion: “Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not. The P versus NP problem continues to inspire and boggle the mind and continued exploration of this problem will lead us to yet even new complexities in that truly mysterious process we call computation.”
It is true, also, that the academic world keeps going even after long-standing problems are proved (primality in P, linear programming in P, for example).
So if it should happen P.ne.NP is proved by an amalgamation of high-level technical tricks … well … there will still be fabulously many wonderful problems in complexity theory to tackle … for reasons that Lance’s article discusses at-length.
And finally, I have to respectfully disagree with Gil on the merits of Scott’s wager … any column that is fun, tricky, and thought-provoking … and that (by careful construction) harms no-one … is good IMHO.
Comment #39 August 9th, 2010 at 12:21 pm
Scott, (oops, please please delete the second copy); I do not see why you should “win” a game that you do not participate; you “win” a lot of games in which you do participate.
And if you really really want to express your honest opinion without being nasty, how about: “In my opinion, it is very unlikely that the argument will stand”.
Comment #40 August 9th, 2010 at 12:24 pm
The most interesting comment for me is the explanation of *why* proving something known to be true is an interesting thing to do (OK, I can rephrase that in a more subtle way, but you know what I mean). The naive purpose, the one that is given most often as an explanation, is to increase the level of certainty we have in the claim, which I find unconvincing (does it really do that? and do we need the increased level of certainty?). I much prefer the view that this methodology leads to interesting ideas.
Comment #41 August 9th, 2010 at 12:56 pm
Gosh, I never knew Scott was such a wimp! Now here’s a bet: “If Wigderson, Arora, Gowers, and Cook spent 10 years in seclusion and emerged with a joint 1000 page proof that P!=NP, with half of the proof reduced to computer-verified formal logic, and even if the authors signed their names in blood beneath every single page of the rest of the proof, then I would still bet every penny I owned and go to the bank to borrow more money to bet even more, that the proof was wrong”.
So, you can see that it’s pretty low odds. But, even lower odds is my alter ego managing to post on such a subject without somehow mentioning linear state spaces!
Comment #42 August 9th, 2010 at 1:02 pm
I don’t see anything nasty about this post, and it tastes delicious too.
Comment #43 August 9th, 2010 at 1:07 pm
Maybe Scott is banking on a Perelman like refusal of the Millennium prize. And I don’t see how letting somebody freeroll for 200k could ever be nasty…. but I’m no expert on science blogging.
Comment #44 August 9th, 2010 at 1:23 pm
This is a great post. So much funnier as well as more informative than a bland “In my opinion, it is very unlikely that the argument will stand”. I must be living in a different planet from those who think it is nasty.
Comment #45 August 9th, 2010 at 1:30 pm
I read a lot of science blogs and I do not find them particular. There only problem as far as I can see is that they are an invitation to procrastinate.
Nor do I see Scott’s offer as being. Scott wanted to communicate that he did not believe in the proof which he effectively did. Just saying he did not believe it would not be as effective in his opinion.
And if you actually thought that expressing his opinion would be sufficient I fail to see how the offer of money is worse. After all, then you believe that Scott would still communicate the same message of discouragement to the proof author.
Comment #46 August 9th, 2010 at 1:30 pm
“Nasty” disappeared from two places in the previous post.
Comment #47 August 9th, 2010 at 1:38 pm
I talk about prizes in the introductory microeconomics class I teach. I will definitely include what you have just done the next time I teach the course.
If more scientists were willing to bet their beliefs we would know a lot more about the world than we currently do.
Comment #48 August 9th, 2010 at 1:53 pm
I think this is a decent post and also an amusing one.
I also didn’t read the post as expressing disbelief in the correctness of the proof.
(Personally, I do not believe the “proof” is correct.)
Comment #49 August 9th, 2010 at 1:53 pm
I didn’t think this was “nasty” when I first read it this morning, nor do I think Scott is unduly horning in on the game. On the former, Scott said all the correct things about Deolalikar and the paper, and I think the $200K offer is serious, not mocking. Indeed I think it would be viewed as a grand geste that would recoup some of the $$$ in positive PR value, in a world turned upside down if the proof strategy turns out to be correct. On the latter, the complexity bloggers feel they have to say something now, Right Now in the 24-hr. Net cycle, and what Scott said about the status is spot-on. Scott has earned the right to weigh in—in a way that’s characteristic :-). Hopefully, though, once the initial queries and terms of conversation are established, the Net will back off and give time and space for in-depth reading. Scott honestly said he couldn’t do that right away, which became the basis for the wit in his post, and I myself have lots of unattended XYZ from July for personal reasons. I hope the author will be given space the way the mathematical community IMHO behaved very well over the June 1993—Sept 1994 timespan it took Wiles (and Taylor) to fix the Fermat bug—of course, that was before blogging… He was in fact rushed out in a leak, and has promised a new version in about a week.
Comment #50 August 9th, 2010 at 1:57 pm
Out of curiosity, is there any situation where you would bet in favor of the correctness of a proof of P != NP which was only a few days old?
Comment #51 August 9th, 2010 at 2:10 pm
Actually, it sounds to me (in a rather stupid way) that Vinay can still miss being $200K richer (even though his proof happens to be correct) if he misses out on getting $1M richer (how sad would that be)…
On a different note, if he gets the Clay prize and his proof is incorrect (lolz) then Scott, for no reason, gives away $200K!
I think, Scott should have said if the proof is correct, he will supplement Vinay’s prize by the amount of $200,000.
Comment #52 August 9th, 2010 at 2:13 pm
To add to David Speyer’s question, is there any situation where you’ll not bet against a potential proof of P!=NP which was only a few days old?
Comment #53 August 9th, 2010 at 2:33 pm
I think there is a fairly straightforward flaw in the argument, although I’m not sure where I should say this sort of thing (so I’ll say it here, since I’m already here and I don’t care enough to spend too much time on the issue). I also feel like I am probably misunderstanding something, since this is a rather obvious objection.
In order to apply the locality theorems for FOL to a fixed point calculation, it is essential that you are inductively defining a unary predicate (otherwise the notion of “local” will change over the course of your induction). The theorem that FOL(LFP) = P relies on defining higher order predicates.
In order to get around this difficulty, Deolalikar passes to a new universe whose elements are k-tuples of elements from the original universe. A k-ary predicate in the original universe corresponds to a unary predicate in the new universe, and so Deolalikar claims that without loss of generality he need only consider inductive definitions of unary predicates.
However, in Section 6 he proceeds to prove a bound on the size of the largest neighborhood in a graph corresponding to k-sat in a very specific way; the universe is simply the set of literals and their negations. If instead we take the universe to be tuples of literals, his claims about the structure of this graph fall apart. In particular, I think the diameter of the graph becomes equal to 2, and the neighborhood of every point now has size O(n) rather than polylog(n).
More simply, if you put Deolalikar’s paper side by side with the actual proof that FOL+LFP = P, something seems very wrong (or at least it does to me). The proof that FOL+LFP = P is based on creating new structure inductively and using this structure to do computation. Deolalikar’s proof is based on the assertion that the structure provided by a random instance of k-SAT is not adequate to do computation on its own, which doesn’t even speak to the methods used to prove that FOL+LFP = P, or consequently to an actual FOL+LFP formula for satisfiability.
I am not saying that the ideas in the paper may not be of independent interest, but I do believe that the argument as a whole is unlikely to give anything like P!=NP.
Correct me if my objection is not justified.
Comment #54 August 9th, 2010 at 2:48 pm
If he isn’t awarded the prize, please pay the $200k to me. Thank you!
Comment #55 August 9th, 2010 at 3:35 pm
Well, Scott, at least if this proof does turn out to be correct, you are off the hook for being on the Clay prize award committee due to a conflict of interest. So that’s one less thing you have to worry about.
Comment #56 August 9th, 2010 at 4:13 pm
KK (#16) (on the reasons a proof of P≠NP would be important):
So, if you don’t mind me rephrasing what you said to see if I understand correctly: It’s not that the answer itself will provoke a dramatic change to the field (as opposed to a proof of P==NP). It’s that a proof would require paradigm-shifting insights about computation, and investigation of these new insights will become the main subject of theoretical CS.
I couldn’t have said it better! “It’s not the destination; it’s the journey.”
Comment #57 August 9th, 2010 at 4:14 pm
@Ungrateful_Person
Qualifying the offer on the basis of correctness rather than the decision of the Clay foundation would defeat the purpose by putting Scott in the position of judging whether the proof is correct.
Comment #58 August 9th, 2010 at 4:31 pm
David S. (#52):
Out of curiosity, is there any situation where you would bet in favor of the correctness of a proof of P != NP which was only a few days old?
The only circumstances I could think of are rather implausible ones (e.g., the proof has been coded up in HOL or Mizar; the proof is only a few pages long and all the experts have verified it in its entirety). In such circumstances, I also don’t know who would take the other side of the bet.
On the other hand, there are some obvious circumstances—for example, Razborov announces a proof, the paper is full of intellectual fireworks from page 1, Raz, Wigderson, and 15 grad students say they’ve already read it and believe it, Mulmuley says he now sees why GCT was the wrong approach from the beginning—where I certainly wouldn’t bet against the proof.
Comment #59 August 9th, 2010 at 4:41 pm
Well, I think Scott’s offer is a bet against this particular proof, since it’s not phrased as an offer to increase the Clay prize by $200k to anyone who collects it. I’d be surprised if Scott was willing to make a similar offer if the proof looked better than it currently does, e.g. if it addressed the relevant TCS concerns about P/NP proofs more directly.
Me, I’m willing to make an open-ended offer but it will be for more like $2 than $200k ;-). I’d also bet against the proof at fairly long odds, e.g. if Scott wants to hedge his own bet then I’d cover a little bit of it at 10-to-1.
Comment #60 August 9th, 2010 at 5:06 pm
I think Scott’s strategy makes great sense. If the proof is wrong, then he pays nothing; if it’s right, then he pays $200k for a) the genius of it, and b) for making the guy look bad by betting $200k against it.
Comment #61 August 9th, 2010 at 5:15 pm
I think Scott know that the guy won’t actually take the money if it is right.
Comment #62 August 9th, 2010 at 5:34 pm
Yeah that too.
Comment #63 August 9th, 2010 at 5:53 pm
“If P≠NP is proved, then to whatever extent theoretical computer science continues to exist at all, it will have a very different character.”
But Scott, most of us complexity theorists aren’t working on proving P not= NP. The topics appearing in complexity conferences (derandomization, cryptographic security, inapproximability of NP-hard problems, proof complexity …)
will likely remain at least as relevant after P not= NP is proved.
Comment #64 August 9th, 2010 at 9:16 pm
Deolalikar says on his website that “Confirmations began arriving 8th August early morning,” so I guess some people think he’s right.
In any case, my question is: Is it possible that a proof so intricate will never be completely accepted by all, even if some consider it correct? i.e. some people (even experts) might always think “it’s such a complicated proof, there’s got to be an error in it somewhere, even if it hasn’t been found yet.”
Comment #65 August 9th, 2010 at 9:21 pm
If P‡NP then you might not be able to verify his proof in polynomial time. 🙂
Comment #66 August 9th, 2010 at 10:04 pm
@Peter “Is it possible that a proof so intricate will never be completely accepted by all, even if some consider it correct?”
I don’t think so. When big proofs come out, if they get past the first round of expert review, there are books written about them, lecture series given on them, reading courses organized. A state of uncertainty such as you describe would keep drawing more scholars into the subject. I think it is very unlikely that there would not eventually be so much interest that it became clear, one way or the other.
There is one result I can think of which is sort of in this state: The classification of finite simple groups. Wikipedia has a decent survey of the history. What I want to emphasize is that mathematicians have not simply given up on the argument. There is a major project at work to simplify and collect all of the results together and make sure that there is a valid proof. Unfortunately, many of the experts on finite group theory are dieing, so the proof gets harder to patch as time goes on.
But the classification proof is huge, and was in a relatively isolated field. And I can’t think of anything else like it. It is hard to imagine this situation occurring with a single 100 page paper, in a growing field like complexity theory.
Comment #67 August 9th, 2010 at 10:21 pm
@Peter, David Speyer
Well, there’s Hales’ computer-assisted proof of the Kepler conjecture. Last I read, it was in a kind of “almost accepted” state, but that attention has moved on to an attempt to formalize the proof in HOL and Coq. Has there been a change of status?
Comment #68 August 9th, 2010 at 10:22 pm
Well, if anyone has finally figured out how to be patient and have a 100+ page proof proofread and verified by independent qualified auditors before publication, that alone might constitute a milestone of considerable novelty in the theoretical sciences.
That said, I’d bet heavily (albeit not that heavily, Scott!) in favor of any lengthy and complex proof containing some errors. The question usually turns out to be whether or not it is fixable.
I was duly impressed with the ideas in the paper though, regardless of their applicability towards proving this particular problem.
Comment #69 August 9th, 2010 at 10:47 pm
It’s kind of like James Randi’s stated explanation for his million-dollar prize in the paranormal. On the one hand, what he says is something like, “I would pay a million dollars to be a part of a conclusive proof that psychics, ghosts, dowsing, etc. exist — a proof that would fundamentally create new plausible dimensions for science. It’s worth paying a million dollars for a small part in that.” But on the other hand, you can’t help but seeing the side motivation of “I am willing to bet a million dollars that you’re a phony, trying to weasel money out of a credulous public. And I want to have this bet, and your unwillingness to be scientifically tested to claim it, as a proof that you’re wrong.”
Honestly, in regard to the above arguments, I’m surprised that nobody has brought up the fact that it might be more rational to bid $200,000 than $20,000. $200k is at the limits of credulity. (It was designed to be that way for a totally different reason.) In this “sweet spot” of the limits of credulity there is a very good chance that the other person will view it as a matter of pride that they turn down the reward: “Look, I’m already earning a million dollars — please save your kind offer for your kids’ college tuition or so.”
I don’t know the exact probabilities and I’m not suggesting that this is the reason that he did it; I am just saying that I find that problem much more interesting than a premature exposition of why this proof is/isn’t wrong.
Comment #70 August 9th, 2010 at 11:00 pm
Can someone make an intelligent comment on Paul Christiano’s comment (#55)?
Comment #71 August 9th, 2010 at 11:20 pm
Ad Rick McGeer(#74), yes Christiano’s comment is substantial and its parts have been echoed by other researchers. Indeed it was arguably the “critical mass” that spurred me to start drafting the body 1.–4. of the update here.
Comment #72 August 9th, 2010 at 11:21 pm
There certainly are a few errors of the “don’t rely on spell check” variety (e.g., in definition 2.16, “man” should be “map”), and probably a glitch in an equation here or there. That’s the problem when you borrow ideas from statistical physics for a proof in theoretical computer science: you might lose a constant factor and end up proving that P = NP/2π.
Comment #73 August 9th, 2010 at 11:48 pm
Blake, yes but there’s the old standby that 1=0=2pi=2Pi i. All constants are the same as long as they show up frequently and are easy to normalize.
(Sorry, I’ll try to stop damaging the signal to noise ratio now…)
Comment #74 August 9th, 2010 at 11:56 pm
Hi Scott, why don’t you bet with me: if Vinay Deolalikar does not get the 1M prize, I pay you $1000. But if he does get the prize, you pay me $200k. In this way, if you correct, you at least win $1000.
============
I am just kidding! I am on your side. I would bet with somebody, who think Vinay Deolalikar will get the prize.
Comment #75 August 9th, 2010 at 11:59 pm
Excellent post. Especially the $200K bet. Bayesians around the world will rejoice.
Comment #76 August 10th, 2010 at 12:23 am
Personally, if I’d written the paper, I’d be very excited about this post. Whatever embarrassment might be suffered if Scott wins is more than compensated by the gain if he loses. I suppose it should be left to Vinay Deolalikar, and not to Scott, to evaluate those payoffs, especially since the paper was “leaked”, but it is hard to imagine he would feel differently about this.
Comment #77 August 10th, 2010 at 12:35 am
Scott, please be careful about making lots of bets like this. There are a number of results showing that if you make lots of bets on what you think are 99% sure things, you will not get through 100 of them before hitting a rock.
Peter de Blanc conducted an excellent illustration of this with regards to the certainties of mathematics. He asked someone for their subjective probability that 7 was prime, and they said “Probability 1.” He asked them if they would be willing to pay $100 if they were mistaken. They said yes. Then he asked them if they’d be willing to pay him $100 if 11 turned out not to be prime, and again they said yes. They were willing to make the same agreement for 13, 17, 19, and 23, but wisely passed it up for 27.
The whole thing is worth reading, but to go ahead and spoil the punchline, they got 51 wrong, Peter told them to donate the $100 to the Singularity Institute, and I told Peter that he was abusing his powers as a subjective Bayesian and that it wasn’t right to take advantage of lesser mortals like that.
Comment #78 August 10th, 2010 at 12:47 am
James wrote, “If more scientists were willing to bet their beliefs we would know a lot more about the world than we currently do.”
In some sense scientists are betting their beliefs by spending time and effort in avenues they regard promising and important.
But in the way James suggested it I think it is very unreasonable to think that scientists betting scientific beliefs will lead to us knowing a lot more about the world. I also do not think this idea is rooted in microeconomics. (James, can you explain how?) To the extend that this idea is based in microeconomics, I think we should look carefully and skeptically at the argument and the relevant microeconomics.
Regarding the 200K offer, ok, maybe I was too harsh to regard it as nasty certainly there are alternative interpretations, and in fact, I do not feel this way anymore.
Comment #79 August 10th, 2010 at 1:28 am
I also agree with Gil Kalai above: this is a nasty post.
Comment #80 August 10th, 2010 at 1:41 am
Steve Cook (#64):
But Scott, most of us complexity theorists aren’t working on proving P not= NP. The topics appearing in complexity conferences (derandomization, cryptographic security, inapproximability of NP-hard problems, proof complexity …)
will likely remain at least as relevant after P not= NP is proved.
Hi Steve! At a “formal” level, I completely agree with you: a proof of P≠NP wouldn’t solve most of the problems that we actually talk about in conferences today. (On the other hand, I see derandomization as one of the exceptions: something we know is more-or-less equivalent to weak circuit lower bounds, and which will probably have to be solved before we can even begin to think about strong circuit lower bounds like NP vs. P/poly.)
My comment about the likely effect of a P≠NP proof on our field had more to do with history and sociology than with formal implications. One could just as well say:
Paul Cohen’s introduction of forcing in the 1960s didn’t address most of the questions that logicians cared about at that time (at least, I don’t think it did—anyone more familiar with the history of logic care to comment?).
Special relativity didn’t solve most of the problems that constituted the research agenda of the average physicist in 1904.
Darwin’s Origin of Species had relatively limited impact on the most pressing problems of botany and animal husbandry of the mid-1850s.
The point is that these were paradigm shifts that eventually changed their respectively fields’ entire concepts of which problems were important. Like the midday sun, they didn’t erase the stars; they just shone so brightly that the stars became vastly harder to see.
My prediction is that a proof of P≠NP would likewise be a paradigm shift for us. Again, this is not because of the statement itself, but because the new ideas developed in the course of the proof would “shine so brightly” that communication complexity lower bounds, inapproximability, zero-knowledge protocols, cutting-planes proof systems, and all the other topics that currently constitute the bread and butter of our field would seem quaint and old-fashioned by comparison.
Admittedly, you have much more experience than I do with which to evaluate such a prediction—what do you think?
Comment #81 August 10th, 2010 at 1:44 am
I hereby bet $17 that no proof that Superman is stronger than Godzilla is correct.
Comment #82 August 10th, 2010 at 1:45 am
I also agree with Gil Kalai above: this is a nasty post.
Well, that was a nasty comment. 🙂
Comment #83 August 10th, 2010 at 2:17 am
Peter (#65):
Deolalikar says on his website that “Confirmations began arriving 8th August early morning,” so I guess some people think he’s right.
I saw that comment too … and to be honest, it was sort of the final straw that inspired my $200k bet. The idea that anyone could “confirm” a 103-page proof after only two days strains credulity. And even if they did, is the vague reassurance of confirmations by unnamed “leading researchers in various areas” supposed to sway anyone? Who does Deolalikar think he’s dealing with? 🙂
Comment #84 August 10th, 2010 at 2:46 am
Maybe he just meant that people confirmed that they had received the draft?
Comment #85 August 10th, 2010 at 3:07 am
When I read that line my first thought was that there was confirmation that “leading researchers in various areas” were confirming that they had received it and had not thrown it into the spam pile.
Comment #86 August 10th, 2010 at 3:11 am
I read it as confirmations of receipt, not confirmations of correctness. Why not be generous in your interpretation of an ambiguous statement, given how posts like this demand similar generosity?
Betting against a colleague is nasty, but perhaps that isn’t what you meant. I think the cash prize is crude in any case; have you not read any of the stories of the Perelman saga?
Comment #87 August 10th, 2010 at 3:28 am
It would be funny if Scott ends up receiving more emails because of this $200k than he would have received without it. 🙂
I don’t think this $200k business is nasty, and I guess that if Vinay is awarded the $1m he would not accept this $200k from Scott. I think this was just a very strong and somewhat funny way of expressing his opinion. Maybe too strong, but not nasty.
Comment #88 August 10th, 2010 at 3:42 am
Obs, arj, John D.: I have no idea why you think he meant “confirmations of email receipt”—who even sends those these days? 🙂 But maybe someone can ask him to clarify.
Comment #89 August 10th, 2010 at 3:53 am
I think the cash prize is crude in any case; have you not read any of the stories of the Perelman saga?
I’ve followed that saga closely since the beginning, and I think Perelman was a fool (or more accurately, a meshugenner) to refuse the prize. There are any number of worthwhile things he could’ve done with the money; if his problem was that not enough credit was given to Hamilton, the decent thing would’ve been to share the prize with him. Contrary to any number of blog commenters, I don’t see that choosing to thumb your nose at the world and subsist on black bread in your mother’s apartment is in any way heroic or noble. Proving the Poincaré was heroic; the other stuff is merely eccentric.
Comment #90 August 10th, 2010 at 4:35 am
Perelman was a fool (or more accurately, a meshugenner) to refuse the prize.
Perelman said the reason why he had taken a long time to consider whether to accept the prize or not was that he had to weigh the advantages and disadvantages of his decision. He obviously knew money had advantages; he’s no fool.
Comment #91 August 10th, 2010 at 4:52 am
I don’t think this proof has the level of content that Perelman’s did.
I do think the $200k thing is a bit discordant. I wouldn’t say “nasty” except in the fairly mild sense of open cynicism which should be considered understandable in this situation.
Comment #92 August 10th, 2010 at 5:09 am
Scott! Put some Google ads on this blog and recoup your losses! The proof is OBVIOUSLY right, it’s over a hundred pages!
Comment #93 August 10th, 2010 at 5:13 am
@Scott: regarding your comment about Perelman. Different people have different opinions, Perelman’s is different from yours, this does not mean he is a fool or is eccentric. He is not irrational, he just thinks differently. You have to understand his views to understand his actions as rational decisions.
Comment #94 August 10th, 2010 at 5:56 am
CT, you cannot assume that one of the disadvantages of Perelman’s decision that he considered was the lack of money. There are other disadvantages that may have been more relevant to him, such as the risk of being called a fool by people who cannot understand his motives.
Comment #95 August 10th, 2010 at 7:10 am
I withdraw the word “nasty” and replace it with “not nice”, which was what I meant all along…
Comment #96 August 10th, 2010 at 8:00 am
I don’t think Scott’s bet is even “not nice”. In fact, it is pretty generous, considering that Vinay’s paper doesn’t seem to be written in a reasonable or rigorous way. Also, it is not a 100+ pages proof. The “proof” is only on the last section.
Comment #97 August 10th, 2010 at 8:20 am
If Vinay wins but refuses your supplement, who does the $200,000 go to?
Comment #98 August 10th, 2010 at 8:48 am
Perelman is certainly no fool. Money can have serious disadvantages especially when everyone knows you get it.
Publicly accepting a million dollar prize makes you an instant target of many nasty people, and in countries like Russia in particular. It would very likely force Perelman to abandon his preferred lifestyle (and few things are more annoying than that).
Besides the fact that there are worthwhile things you could have done with the money, may be all the more reason to refuse them if you don’t feel like you are the right person to do it or don’t want to.
There is nothing crazy about his decision. You are a fool for projecting your own valuations onto him.
Comment #99 August 10th, 2010 at 8:51 am
How about we try to prove/disprove another way as the problem has perplexed as well as amused John Nash and have him review. He’s easy enough to reach, that’d be a pretty interesting counter paper to read.
Comment #100 August 10th, 2010 at 10:29 am
Nice post. Now I’ll be sure to forward you a copy if I solve a Millennium Problem…
Comment #101 August 10th, 2010 at 11:28 am
Reply to Scott’s Comment #80
It would be nice if a proof of P not= NP had the influence of Darwin’s “Origin of Species”, but that’s probably too much to hope for.
Comment #102 August 10th, 2010 at 11:36 am
#66 Would you not expect the proof to be easily verified 😉 Part of me would love it to be proved but most of me likes these things to still be out there.
Comment #103 August 10th, 2010 at 11:55 am
Yeah…
How dare some douche outside the holier-than-thou academia even attempt to exercise his brain? How dare he work on problems that are exclusively my turf?
God forbid if he is (even partially) right! Will that make me an idiot? Will I cry at night? Will I hate my parents who brought me into this world to face such a failure?
And what is this world coming to? How can brain-dead slaves from the industry, the wretched industry!!! can work on fundamental problems that we even we, the true “ubermenschen” of human race, have given up on?
Does that mean God really exists now? I feel worthless.
Comment #104 August 10th, 2010 at 12:06 pm
I tried to understand/reformulate the approach, and here
is my, perhaps very minimalist, attempt: the discrete probabilistic distributions in the paper can be viewed
as tensors, or very special multilinear polynomials.
The assumptions “P=NP” somehow gives a (polynomial?)
upper bound on the tensor rank. And finally, using
known probabilistic results, he gets nonmatching
(exponential?) lower bound on the same rank.
If I am right, then this approah is a very clever, in a good sense
elementary,
way to push the previous algebraic-geometric approaches.
Comment #105 August 10th, 2010 at 1:05 pm
Bob (#103): Chill out, dude.
First, Deolalikar is an academic, albeit one who happens to work at an industry lab (HP). Second, he, and everyone else, should work on anything they want to. Third, within a day of the proof coming out, Lipton, Regan, Cris Moore, and other experts put aside whatever else they were doing and tried to understand it—so this story illustrates the exact opposite of the point you were trying to make. Fourth, if Deolalikar is right, I’ll be $200k poorer, so once again, chill dude…
Comment #106 August 10th, 2010 at 1:14 pm
“Obs, arj, John D.: I have no idea why you think he meant “confirmations of email receipt”—who even sends those these days? But maybe someone can ask him to clarify.”
If somebody sends me a five-page paper for comments, I’ll try to glance at it and get back to them within a week or so. There is no need for a confirmation of receipt. If I see that a paper will take me much longer, then it is polite to send something (“I got your mail, and I’ll look it over in the next few weeks/months”). A confirmation is more important sent to someone you don’t know at all or very well, because they might otherwise worry about spam filters, acts of God, etc.
Comment #107 August 10th, 2010 at 1:21 pm
Just curious. If statistical physics was powerful enough to attack P != NP, then there would be alternate proofs of simpler proofs of the known complexity results in the literature. Is that the case?
Comment #108 August 10th, 2010 at 1:28 pm
Leonid Gurvits’ post expresses an insight that has considerable practical value to quantum systems engineers: stochastic trajectories on low-rank multilinear manifolds (and their associated probabilistic distributions) can be simulated efficiently, otherwise not. It’s fun to appreciate that this insight may have broad-spectrum applicability.
I hope Leonid won’t mind my mentioning—for the benefit of students—that his proof that the quantum separability problem is NP-hard is widely celebrated and admired … IMHO it’s a good example of a proof that (in Scott’s words) “shines so brightly that the stars became harder to see.”
Comment #109 August 10th, 2010 at 1:31 pm
As far as I can tell, nobody’s quite managed to work out what exactly the statistical property of k-SAT he’s using is. That said, Deolalikar does claim, in his update, to be aware of the issues with XORSAT et al., and futher claims that it’s not actually a problem. Whether everyone else agrees remains to be seen.
Comment #110 August 10th, 2010 at 1:36 pm
Anyway, it seems that the “proof” is toast. As I mentioned before, the big (meta-)problem of this paper is hand-waving: when you get to the details you see that the arguments are not spell out in a precise enough manner. This led to a comment I’ve just seen on Lipton’s blog, made by Charanjit Jutla (of IBM T.J. Watson). He talks about an easy to spot (unfixable) problem in the proof, caused by a non careful use of fixed point logic.
Comment #111 August 10th, 2010 at 1:49 pm
interesting, he has removed any mention of this paper from his webpage as of now.
Comment #112 August 10th, 2010 at 1:50 pm
@Dave: But as Ken Regan points out, it might be possible to salvage NL != NP assuming the other objections are fixable.
Comment #113 August 10th, 2010 at 2:17 pm
CT, you cannot assume that one of the disadvantages of Perelman’s decision that he considered was the lack of money.
I was not assuming anything, just paraphrasing what Perelman said as reported in the news media.
Comment #114 August 10th, 2010 at 2:27 pm
Maybe not (reserving any judgement about most of the argument, which I have not understood). Immerman-Vardi says that (FO+order,BIT)(LFP) = P, and it is not hard to show that (FO+successor)(LFP) = P. So this argument might not need to have an ordering in its definition, if it has successor, and thus the Hanf and Gaifman arguments in Chapter 4 might make sense.
But if you were to use the TC-based characterization of NL, as Ken Regan suggests, you have the problem that while (FO+order,BIT)(TC) is equal to NL, (FO+order)(TC) is not NL (it cannot do the unary language of perfect squares — see Lautemann-McKenzie-Schwentick-Vollmer) and thus a forteriori (FO+succ)(TC) is not NL.
Comment #115 August 10th, 2010 at 2:36 pm
Scott, your blog is persistently getting an intermittent wordpress failure, “Error establishing a database connection”. Hitting reload usually works after a try or two.
Comment #116 August 10th, 2010 at 2:59 pm
I predict that what will survive in the proof is
the lower bound(in the language of my prev. post);
and that bound can probably be understood
as one of circuit lower bounds; perhaps the proof
technique could be useful in future.
I was very surprised seeing reasonably general TCS applications
of the boosting, which is so trivial(elementary) mathematically. Bayesian networks…HMM, hope
that they won’t get such a powerful boost…
Comment #117 August 10th, 2010 at 3:47 pm
This post got me thinking…
Besides the Clay prize and Scott’s offer, it seems one could make money from a proof or even an attempted proof of P != NP or even any other result considered interesting, but not quite a “Millenium Problem”:
One posts a first draft of a paper on a website and offers to accept the highest bidder as a co-author. The first author needs to carefully include enough details and ideas to get people excited, but past that, the more vagueness and mistakes, the better, since that makes the potential contribution of a co-author that much more important.
Besides co-authorship, one could offer donors the right to name the principal lemma, so that corporations could participate.
There would be howls of “crass”, “nasty” and “greedy”, but it could be justified in the same spirit as a university naming a building (or even an academic department) after a generous benefactor; it’s all supporting scientific progress.
The price extracted could even be used by as a gauge of the perceived importance of the result, or how likely the proof is correct or at least, correctable.
Comment #118 August 10th, 2010 at 3:53 pm
Everyone is missing the point of the post. I mean we now know that if we annoy Scott enough by email, HE WILL ACTUALLY PAY US TO STOP EMAILING HIM. I, for one, am now, as we speak, surfing the web looking for a good spambot to repeatedly email Scott. Combined with a context free grammar for generating quantum computing questions, I expect to be able to extort vast sums from Scott. Or at least a beer.
Comment #119 August 10th, 2010 at 4:14 pm
Any idea why Deolalikar removed the paper from his webpage? Anyone?
Comment #120 August 10th, 2010 at 4:27 pm
One can still find various versions of the paper in his “Papers” subdirectory.
Comment #121 August 10th, 2010 at 4:32 pm
CM, if Deolalikar realized there is a fatal flaw in the proof, then it must be really heartbreaking for him.
In all this discussion nobody seemed to mention that the guy has probably gone sleepless for the last several weeks or whenever it had dawned on him that he might be on the verge of achieving the Holy Grail of Computer Science. If now all this “high” is mercilessly aborted by the realization that the proof is wrong, I really feel bad for him. Not a feeling to be wished on anyone…
Hopefully, he took it down to correct whatever flaws are correctable.
Comment #122 August 10th, 2010 at 5:16 pm
Is there some hand waving argument that can convince a novice that 3SAT is NP complete but 2SAT is in P? It seems like one of those results that is “surely wrong” other than the fact that you can prove it’s true.
Comment #123 August 10th, 2010 at 5:22 pm
Scott: I initially thought the “bet” was merely in poor taste, it would have been enough to merely state “Given the history of prior attempts, I am very skeptical whether this one will succeed.”
But your comments and updates seem to have taken an increasingly harsh and adversarial tone. This is in contrast to Lipton, Regan,Cook etc all of whom have been very positive.
Even if the proof is incorrect, perhaps we can learn something and gain inspiration. And if nothing else, it is some nice publicity for our favorite problem!
Comment #124 August 10th, 2010 at 5:27 pm
Let us not forget that Andrew Wiles took several MONTHS to correct his proof (he had even had to call his old student to help him).
But unlike that case this manuscript is publicly available so the community as a whole can try to “fix” it and see what can be salvaged.
Comment #125 August 10th, 2010 at 5:27 pm
Hand-wavy argument to (#122). 3SAT is the prototypical NP-complete problems. 2SAT can be solved by greedily guessing an assignment of a single variable, and seeing what other assignments are restricted by this choice. If contradiction is reached, the guess must be wrong, so the other value must be correct. Details are a good exercise for an interested novice. You can then think about how this does not work for 3SAT.
Comment #126 August 10th, 2010 at 6:03 pm
Fans of math-and-physics history will recall the story of John Maddox’s claimed exact solution of the celebrated 3D Ising Model, which he announced at the 1952 StatPhys II meeting in Paris.
Before the meeting even ended, it had become apparent that Maddox’s claimed solution was wrong, and worse, was wrong for mundane reasons. And yet, Maddox went on to a distinguished career as (among other achievements) editor of Nature. As for the 3D Ising Model, it remains unsolved (except numerically and perturbatively) to the present day.
The point of this story is that even if Vinay Deolalikar’s proof should prove to be irreparably wrong—and the jury is still out—then as long as its gap(s) are interesting (which certainly seems to be the case), then IMHO he need not worry about any adverse consequences whatsoever.
I for one am very grateful both to Vinay and to Scott, and to everyone else who is posting thoughtfully, and I think this is how most people feel.
Comment #127 August 10th, 2010 at 6:05 pm
Bob, Wiles’ and Perelman’s situations were completely different from this. Both of them were deep in the technical weeds that other people working on their respective problems had faced. Deolalikar by contrast brought in a bunch of exotic machinery from the “outside”, not necessarily a bad thing since the complexity community obviously hadn’t been finding the right ideas on the “inside”. But they knew about a lot of obstacles that Deolalikar didn’t directly address (leaving open the possibility that he got around them somehow). Wiles and Perelman knew about the obstacles and confronted them directly. As soon as their papers went up, people KNEW that substantial progress had been made, even if the hoped-for endpoint wasn’t quite reached.
Scott: Deolalikar is obviously smart and thought hard about the problem and apparently made several attempts over the past couple years before sending this current one around. I guess this gives him a rather tough baptism into the thorny problems of lower bounds proofs. What happens if he stays in the field and eventually patches this thing into a real proof and wins the Clay prize but the final version has substantial differences from the current one? Are you still on the hook? It seems like you can’t repeat this type of open bet too many times, since that could leave several simultaneous instances open indefinitely.
Comment #128 August 10th, 2010 at 7:11 pm
Scott, you may want to bet 57000$ on the other fives 😉
http://smarkets.com/current-affairs/clay-prize/next-winner
Comment #129 August 10th, 2010 at 7:48 pm
“eventually patches this thing into a real proof and wins the Clay prize”
Well, wouldn’t Scott’s earlier comments about a P≠NP proof changing his life “so dramatically that having to pay $200,000 will be the least of it” mean that he might as well pay an extra bonus to whoever ends up winning the Clay prize? 🙂
Comment #130 August 10th, 2010 at 8:28 pm
@Dave (#118):
Hahaha.
@Mitch (#122):
For the completely uninitiated, a better starting place might be 2-colorability vs 3-colorability rather than variants of SAT. Here’s some POWER-hand-waving for you:
2-colorability = P
3-colorability = NP
Given a graph composed of vertices and edges (that connect arbitrary vertices), the k-colorability problem is “Can you assign colors to vertices so that no adjacent vertices share a color, using no more than k colors?”
For 2-colorability (let’s use red and green), the algorithm is fairly obvious: Pick a vertex, color it red. Color all the adjacent vertices green. Color all the adjacent vertices to those red. Repeat until the graph is fully colored. If at any point you try to color a red vertex green or vice versa, answer with “No;” otherwise, answer with “Yes.”
You can think of this as similar to identifying a string of Christmas lights, with alternating green and red. But with 3-colorability, you run into the problem that “branching” is allowed, i.e. you can’t just think along a single line anymore. With 2-colorability, if you run into needing to color a red vertex with green, you know you can’t fix it. With 3-colorability, there’s the possibility that if you “back up” and re-organize your previous colorings, that you might be able to fix the contradiction you wound up at. So, it’s (or, at least appears to be) quite a lot harder to generate solutions for 3-colorability than 2-colorability.
Not an elegant description… but hopefully it’s useful for thinking about 2SAT vs 3SAT (the logic is the similar).
Comment #131 August 11th, 2010 at 12:02 am
Daniel: Thanks, that was good and easy to understand.
Comment #132 August 11th, 2010 at 12:26 am
http://www.saudigazette.com.sa/index.cfm?method=home.regcon&contentID=2008062910436
Comment #133 August 11th, 2010 at 1:04 am
If Deolalikar’s proof starts to hold up, then the 200k bet will provide Scott incentive to read the paper carefully. He will win 200k by pointing out errors. Thus, Scott’s bet ensures that if it comes to that, he will himself read Deolalikar’s paper carefully. So secretly Scott hopes that the paper begins to hold up but is wrong, so that he can win his 200k.
Comment #134 August 11th, 2010 at 1:24 am
A precedent has now been set. If Scott ever fails to offer a $200k supplement for any announced solution to a Clay Millenium problem, then that constitutes a declaration by Scott that the solution is correct.
Comment #135 August 11th, 2010 at 1:25 am
e.g., the proof has been coded up in HOL or Mizar
If it were coded up in Mizar (and certified of course), then for starters my uncle would be very happy.
Comment #136 August 11th, 2010 at 1:50 am
I’ve always pictured an eventual proof of P != NP as being simple and intuitive, written with crayons (such that Scott could understand).
Really, 103 is alot, one could explain the behavior of women in that many pages, P vs NP should just take a fraction of that.
Comment #137 August 11th, 2010 at 1:50 am
I hereby bet $19 that P equals/does not equal NP will NEVER be solved. I’m still thinking about how I am going to collect on this. OK, not never, but not before the Andromeda Galaxy moves into the Northern Hemisphere.
Comment #138 August 11th, 2010 at 3:16 am
Why?
Comment #139 August 11th, 2010 at 3:57 am
I start disliking what Lipton is doing. At this point it’s clear that the work has no more merit than other P vs NP “proofs” regularly popping up on arXiv and elsewhere. Yet he is pushing the author and others to spend more time on this hype. I hope, if not Scott, then at least Russell Impagliazzo’s latest comments will be heard.
Comment #140 August 11th, 2010 at 4:27 am
A precedent has now been set. If Scott ever fails to offer a $200k supplement for any announced solution to a Clay Millenium problem, then that constitutes a declaration by Scott that the solution is correct.
Sorry, try again! 😉 If I fail to offer a $200k supplement, that constitutes a declaration by me that I wasn’t sufficiently annoyed by blog/news coverage of the solution to offer such a supplement, and/or I’m not on “vacation.”
Comment #141 August 11th, 2010 at 4:46 am
Love the title of AOL News article:
P=NP=WTF?
Beautifully captures the essence of the problem.
http://www.aolnews.com/surge-desk/article/p-np-wtf-a-short-guide-to-understanding-vinay-deolalikars-mat/19586401
Comment #142 August 11th, 2010 at 5:46 am
Anonymous Coward Says: “I hope, if not Scott, then at least Russell Impagliazzo’s latest comments will be heard.”
Yes … logically speaking, we have to agree with a mathematician of the stature of Impagliazzo when he says “I am somewhat distressed to see so many people spending a lot of time on this … I don’t see any real statement of a series of lemmas that imply the main theorem.”
And yet … historically speaking, we have to agree with Dick Lipton too: “Whatever happens I believe that the community should be excited and pleased that a serious effort has been made.”
Since lots of people are writing about the logical point-of-view, I will write a little bit about the historical point of view.
My concrete recommendation (especially for students) is to read two articles by Florin Diacu in the Mathematical Intelligencer, titled “Painlevé’s conjecture” (1993) and “The solution of the n-body problem” (1996). In the latter article Diacu quotes an 1895 critique of Poincaré’s dynamical theorems:
————-
“As in so many of his (Poincaré’s) papers, he gave free rein to his imaginative powers and his extraordinary intuition, which only very seldom led him astray; in almost every section is an original idea. But we should not look for precise definitions, and it is often necessary to guess what he had in mind by interpreting the context. For many results he simply gave no proof at all, and when he endeavored to write down a proof, hardly a single argument does not raise doubts. The paper is a blueprint for future developments of entirely new ideas, each of which demanded the creation of a new technique to put it in a sound basis.”
————-
If we are *very* lucky, such “original ideas” may be what Vinay Deolalikar has provided to us. In his 1947 article The Mathematician von Neumann called it “the rejuvenating return to the source: the reinjection of more or less directly empirical ideas … [that] preserves the freshness and vitality of the subject.”
As Dick Lipton’s blog documents, there are quite a few high-power mathematicians who are impressed by the freshness and vitality of Deolalikar’s ideas. These ideas clearly have deep roots in math and physics; perhaps from these deep roots a proof will grow that everyone can be happy with.
Comment #143 August 11th, 2010 at 7:06 am
I, a poor person, will give Scott $200,000 if he ever comes up with a revolutionary new idea or proof. Reading Scott’s post, I think it should be evident why I am feeling so confident.
Comment #144 August 11th, 2010 at 7:32 am
scott aaronson is kind enough to continue to share his thoughts through this blog.
let us remember to be grateful that the internet makes expert opinions easily available to us, a service we will easily lose if we become emotional when they do not immediately agree with us.
and, dearest other poor person, i was once a rich man, but i took it upon myself to render your promise truthful by acting as your surrogate, i.e. giving all my money to scott aaronson. for, upon surveying arxiv, i confirmed that indeed, he has contributed many revolutionary ideas. I wish I were telling the truth in this paragraph.
as a parting thought, this event (regardless of the mathematical content) has indicated the disturbing power of viral information on the internet. i am thankful for the speed of light, and suddenly nervous about quantum entanglement (a comment which, we could wish, were the actual most painful one on this specific blog….)
Comment #145 August 11th, 2010 at 7:36 am
@144, i read my post in a panic, wondering how many people can’t identify what i meant by ‘telling the truth’.. to be clear: i genuinely wish i could contribute the money for poor person #143…
Comment #146 August 11th, 2010 at 7:51 am
Post #144 reminds us of how pointless it is—and yet how easy—to write a purely snarky post. And conversely, post #144 reminds us also of how valuable it is to the entire STEM community—and how much work is entailed too—that Scott (and other bloggers too) trouble to create forums like this one. They deserve everyone’s appreciation and thanks.
Comment #147 August 11th, 2010 at 8:52 am
I have nothing interesting to add to the discussion, but I would like to salute you all. Reading Aaronson’s post, and the debate above has left me stumped — you guys are amazingly intelligent. Keep up the fantastic work.
Comment #148 August 11th, 2010 at 9:28 am
#143
If it is for me to judge, you should already pay the 200K.
Comment #149 August 11th, 2010 at 10:24 am
Posting in an epic thread.
Comment #150 August 11th, 2010 at 10:50 am
Jeff (Post 125)
Daniel (Post 130)
Thanks for the tips!
Comment #151 August 11th, 2010 at 2:04 pm
These journalists are so funny. I never thought this may go so far to end up on BBC!
http://www.bbc.co.uk/news/science-environment-10938302
Comment #152 August 11th, 2010 at 2:13 pm
Other than its title, the contents of the BBC article seems to be reasonable and good publicity for mathematics and theoretical computer science.
I think HP should pay Vinay for this publicity.
Comment #153 August 11th, 2010 at 2:22 pm
And also the telegraph! http://www.telegraph.co.uk/science/science-news/7938238/Computer-scientist-Vinay-Deolalikar-claims-to-have-solved-maths-riddle-of-P-vs-NP.html
Comment #154 August 11th, 2010 at 2:25 pm
#152
“I think HP should pay Vinay for this publicity”
I don’t think he works for free 🙂
Comment #155 August 11th, 2010 at 2:40 pm
Hello
Please note I am a dumb idiot who doesnt know what he is talking about. But if I may , can I ask a silly question
In Mr. Vinay Deolalilkars paper he says “solution to P Vs NP problem will decide if human creativity can be automated or not”. So does it mean that NP stands for human creativity and P stands for what a computer is able to do?
As a beginner where can I read up on these things.
Thank You
Rama Iyer
Comment #156 August 11th, 2010 at 3:05 pm
John Sidles #142:
I am including The full comment by Russell Impagliazzo on jrlipton.wordpress.com . He is not just saying the paper is not rigorous; he is also saying the intuition and ideas expressed are ones that already exist, for what it’s worth. I certainly don’t have an opinion one way or the other.
“Russell Impagliazzo permalink
August 11, 2010 12:00 am
I am somewhat distressed to see so many people spending a lot of time on this. It does not actually look like a serious attempt at P vs. NP to me. It does not seem to have any original ideas, just an intuition that has been often expressed that search spaces broken up into many clusters far apart are hard for standard search algorithms (but as has been pointed out, can also be exhibited by problems in P, such as solving linear equations.) I don’t see any real statement of a series of lemmas that imply the main theorem, and the conclusions reached do not seem to be supported by any claims made earlier.
I’d like to see a clearly articulated lemma that states the properties used that imply a problem is not solvable in P. In particular, it should be possible to see that the properties
fail for random linear equations, or other easy instances of search problems.”
Comment #157 August 11th, 2010 at 3:11 pm
Dear Rama,
Yes, this is what it means. Though be aware that these are just theoretical (or mathematical) models which try to characterize in some very loose sense “human creativity” and “computer ability”.
Maybe you can start reading the wikipedia entry on P vs. NP.
Comment #158 August 11th, 2010 at 3:31 pm
#155
“In Mr. Vinay Deolalilkars paper he says ‘solution to P Vs NP problem will decide if human creativity can be automated or not’. So does it mean that NP stands for human creativity and P stands for what a computer is able to do?”
I noticed this line as well, and sneered a tiny bit. Speaking as an AI guy, we don’t really know how human creativity works, so claiming any relationship to either P or NP is “premature.” I found that line surprisingly hand-wavy for a theoretical proof. Show me a model for human creativity first, and then we can discuss whether there’s a polynomial algorithm for evaluating it or not.
Comment #159 August 11th, 2010 at 3:33 pm
Dear Dave #157 and Rama #155
No it doesn’t. A hard problem means looking for a needle in a haystack, in which the only possible way to find the needle is to look pretty much everywhere.
Creativity doesn’t make such hard problems into polynomial problems. If it could then it wasn’t a hard (NP) problem in the first place.
And in any case creativity is just computation to the nth degree. (Like trillions of brain cells nth degree)
Comment #160 August 11th, 2010 at 3:36 pm
Aha. So that’s what a permalink is! How useful! I was just thinking to myself, I wish there were a way to forward comments on other blogs rather than to paste them! 🙂
Here are Terrence Tao’s comments. I think they sum up the situation well:
http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/#comment-4885
Comment #161 August 11th, 2010 at 3:37 pm
Vladimir, certainly no slight was intended of Russell Impagliazzo or Dick Lipton …they were quoted only briefly because, heck, the main point is that it is logically consistent (and common-sense too) to agree with both of them.
Bob Sloan (a former NSF Director for TCS) has just posted to pretty much the same effect on Dick Lipton’s blog … but rather than excerpt Sloan’s post, I’ll post this link.
Comment #162 August 11th, 2010 at 3:39 pm
#159
“And in any case creativity is just computation to the nth degree. (Like trillions of brain cells nth degree)”
When I was a grad student, one of the guys on my committee used to say, “never say ‘just’ about anything having to do with human cognition.” Creativity is not “just” anything, unless you have actually implemented it and it works.
We now return you to your regularly scheduled debate already in progress 😉
Comment #163 August 11th, 2010 at 3:40 pm
There’s a significant chance that human creativity can be automated independently of the result of P vs NP.
For example, the intuition, instinct and efficiency that humans display in solving certain difficult problems, such as image recognition, don’t really scale, plus the resulting solutions are often approximations – these are properties that many polynomial time algorithms exhibit on the same problems.
Additionally, when it comes to other tasks, such as proving math theorems, there seems to be substantial coin-flipping and trial-and-error, to the point where the inspiration comes in the form of a well educated guess.
In my opinion, the main obstacle in automating creativity is that computers aren’t yet sufficiently educated – because otherwise they can certainly flip coins and even efficiently validate their own guess for a solution to a hard problem (that’s the beautiful side of NP) – they just need more data.
Comment #164 August 11th, 2010 at 3:44 pm
@Marc Goodman #157:
Many, e.g. Godel, have expressed similar opinions that P=NP would mean that computers can find any reasonable size proof that mathematicians are capable of finding in practice. I think this reference to human creativity should be understood in this context not AI one. It is not about general human creativity say in art but only about finding formal proofs. It also does not mean that NP corresponds to mathematical creativity, it only needs to be an upperbound on our ability to find proofs within reasonable amount of time.
Comment #165 August 11th, 2010 at 3:53 pm
@ #164
But Vinay/someone else has/will proved/prove P!=NP
so the relation to creativity is mootful.
Comment #166 August 11th, 2010 at 3:54 pm
Job #163:
There’s a significant chance that human creativity can be automated independently of the result of P vs NP.
I completely agree with you, and I think anon #164 did an excellent job of clarifying what we mean when we say this.
Comment #167 August 11th, 2010 at 3:55 pm
#163
“In my opinion, the main obstacle in automating creativity is that computers aren’t yet sufficiently educated – because otherwise they can certainly flip coins and even efficiently validate their own guess for a solution to a hard problem (that’s the beautiful side of NP) – they just need more data.”
At the risk of beating a dead horse, you’re totally begging the following fundamental questions which are at the heart of AI:
What are adequate methods for representing knowledge?
What methods can be used to efficiently acquire such knowledge?
Once that knowledge has been acquired, how can it be manipulated usefully/interestingly?
There are lots of theories for all three of the above questions, all of which have been demonstrated to work at least on “toy” examples, but there is no consensus on any of those theories. Even if you assume the above to have been “solved,” which it isn’t, then you still have to answer the question of “what constitutes creativity? Is merely deriving a relationship between two or more previously unrelated entities creativity? Or, is the successful adaptation of previous experience creativity? Can one truly be creative without having a body to experience the world in? To what extent is creativity a reaction to the world around us, rather than a ‘mere’ manipulation of symbols and propositions?” etc., ad nauseam.
People look at art, for example, and say, “that’s really creative,” or “that’s derivative.” Experts disagree on what’s creative in the art world. If we can’t even agree on the products of creativity, what chance do we have to define the mechanism?
Comment #168 August 11th, 2010 at 3:58 pm
Gosh, suddenly there seems to be a phase transition to an ordered state of civility and reason through the “Deolalikar blogosphere”… it’s very impressive!
Searching my database for an apropos quotation, I find Feynman’s Nobel Lecture:
—-
“There is always another way to say the same thing that doesn’t look at all like the way you said it before. I don’t know what the reason for this is. I think it is somehow a representation of the simplicity of nature. … I don’t know what it means, that nature chooses these curious forms, but maybe that is a way of defining simplicity. Perhaps a thing is simple if you can describe it fully in several different ways without immediately knowing that you are describing the same thing. … We are struck by the very large number of different physical viewpoints and widely different mathematical formulations that are all equivalent to one another.”
——
Feynman was speaking of quantum dynamics, but surely the same is true of complexity theory too … and Vinay Deolalikar’s proof technology (with its blend of physical and mathematical elements) is shaping up to be an outstanding example of it.
As in any STEM enterprise, it is not necessary that everyone think alike, use the same mathematical tools, or pursue the same objectives. Such uniformity is not even a good idealized goal (uhhhh … so long as we are pretty confident that P≠NP, at any rate).
Comment #169 August 11th, 2010 at 3:58 pm
Job, good point: My guess is that the “P vs NP” issue is orthogonal to the “automate human creativity” issue.
Scott: The jigsaw puzzle analogy for P vs NP is great, which I will use the next time anyone asks me about it.
Comment #170 August 11th, 2010 at 3:59 pm
“..shine so brightly..”
The szenario that it would still take some decades until someone comes up with a proof that P ne NP is somewhat similar to Perelman’s proof ot the Poincaré conjecture. People in that field have assumed the conjecture for so long that the impact of the proof was rather limited (i think). The difference between TCS and geometric topology is that TCS as a part of CS is at least partly about practical matters, namly efficient real world computations. If TCS would be upset by a long expected, negative result like NP ne P, the TCS world might be leaning too far to the math side.
Comment #171 August 11th, 2010 at 4:00 pm
#164
“Many, e.g. Godel, have expressed similar opinions that P=NP would mean that computers can find any reasonable size proof that mathematicians are capable of finding in practice. I think this reference to human creativity should be understood in this context not AI one.”
OK, that makes sense. Creativity with respect to theorem proving may or may not be the same as general creativity. Since I don’t have an adequate, working model for either one, it would be foolish of me to claim any isomorphism or lack of same 😉
Comment #172 August 11th, 2010 at 4:01 pm
I never heard of P versus NP before this morning. All I can say is I have since learned that it is an important issue and a proof (whether it is from this HP dude or someone else) can have serious ramifications on several fields. Such publicity/information in itself is important.
Comment #173 August 11th, 2010 at 4:07 pm
Tim Gowers has now also posted a blog entry reacting to the attention to the paper:
http://gowers.wordpress.com/2010/08/11/my-pennyworth-about-deolalikar/
Comment #174 August 11th, 2010 at 4:42 pm
Vinay has a new version (Aug 11) on his HPL web page.
Comment #175 August 11th, 2010 at 4:57 pm
Breathtaking! I hope Vinay has addressed some of the concerns…
Comment #176 August 11th, 2010 at 5:28 pm
Does anyone know what the three lines of Hindi (?) on the dedication page of his paper say? Online translation tools are not helpful. Just curious.
Comment #177 August 11th, 2010 at 5:30 pm
No it doesn’t. A hard problem means looking for a needle in a haystack, in which the only possible way to find the needle is to look pretty much everywhere.
Sorry, I did not understand your answer. What Rama asked about is what is claimed in Vinay’s paper; which is in fact what is claimed popularly in many places discussing P vs. NP. E.g., in Wigderson’s paper “knowledge, creativity and P vs. NP”. I’m citing:
The seemingly abstract, philosophical question: Can creativity be automated? in its concrete, mathematical form: Does P = NP?, emerges as a central challenge of science.
So, the answer is “yes”. This is what people mean by connecting P vs NP to creativity and computers. The fact that the connection is not necessarily true is independent of this question; and I did not want to confuse Rama as a beginner.
For Rama:
I have just found a very good source for reading on this from the expert (Avi Wigderson), and in a popular way:
http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW09.pdf
Comment #178 August 11th, 2010 at 5:39 pm
To comment # 176:
The letters seem Hindi…but it probably is Sanskrit
Comment #179 August 11th, 2010 at 5:42 pm
Already translated in quantum pontiff blog comments
Comment #180 August 11th, 2010 at 5:50 pm
Thank you, guys (#178-9), and pardon my ignorance.
Comment #181 August 11th, 2010 at 6:06 pm
@CT (Comment 176)
Thats because its Sanskrit, not Hindi. Anyway, they are lines from a Hindu holy book called the Bhagvad Gita.
Translation:
Line 1: I am not sure what it means.
Line 2, 3: You have a right to perform your prescribed action, but you are not entitled to the fruits of your action.
Never consider yourself the cause of the results your activities, and never be associated to not doing your duty.
Comment #182 August 11th, 2010 at 6:15 pm
It looks like he posted an updated version of his proof here:
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
Comparing this update and the update before that, it has changed quite drastically, for instance his chapter 2.6 called “Parametrisation” has turned into a whole chapter by itself (chapter 3, so the paper now has 8 chapters instead of 7).
Comment #183 August 11th, 2010 at 6:19 pm
CT asked: Does anyone know what the three lines of Hindi (?) on the dedication page of his paper say? Online translation tools are not helpful. Just curious.
An answer to that question was provided on Dave Bacon’s blog Quantum Pontiff, by the systems biologist Mathukumalli Vidyasagar (permalink here).
Vidyasagar’s answer is so thoroughly excellent that I prefer not to abridge it.
Comment #184 August 11th, 2010 at 6:22 pm
@RDN (Comment 182), I feel like I’ve read about a community of people who held this same belief in Altur’Rang.
@Scott throw back to “sword of truth”
Comment #185 August 11th, 2010 at 6:24 pm
After reading John Sidles permalink (Comment 184), I retract my earlier statement 😛
Comment #186 August 11th, 2010 at 7:31 pm
Anyone noticed yet?
There is a minor modification to his HP webpage, shortly before all the objections came out on 8th Aug: he added “Indian citizen.” to his Brief Bio, was he already preparing for a celebration or what?
Comment #187 August 11th, 2010 at 8:10 pm
Not sure why you think it’s odd that someone who’s getting tons of media attention spends a few seconds on fine-tuning their bio…
Comment #188 August 11th, 2010 at 10:52 pm
Would somebody like to honestly comment—
had this been a proof of P==NP, would Deolalikar still get so much of attention from so many high profile academicians, in such a short time?
Comment #189 August 12th, 2010 at 2:09 am
Consider this from Georgia Tech’s Richard Lipton and Ken Regan from SUNY Buffalo .
“We think that Vinay Deolalikar should be thanked for thinking about this difficult problem, and for sharing his ideas with the community. Whether he got it right or not, he has tried to add to our understanding of this great problem. We need more people working on hard problems. If no one does, then they never will be solved.”
Comment #190 August 12th, 2010 at 3:21 am
Scott said: “What’s emerged as the perhaps central issue is the bane of so many attempted P≠NP proofs in the past: namely, why does the proof not work for 2SAT, XOR-SAT, and other problems that are very similar to 3SAT in their statistical properties, yet for which polynomial-time algorithms are known? If Deolalikar can’t provide a clear and convincing answer to that question, the proof is toast.”
I think a proof’s correctness doesn’t depend on the author being able to explain why the proof doesn’t work in other situations where proof is not supposed to work. Of course, if the author can show why the proof doesn’t work when it is not supposed to, it may give more insights and help people understand the proof’s inner workings. But it is not required for correctness.
I don’t know too much about the history of failed attempts at proving or disproving P = NP, but I’m guessing that previous attempts to explain why the proof does not work for 2SAT, XOR-SAT have exposed flaws in the proof? If that is the case, then I can understand why the author in this case would be expected to provide such explanations. Otherwise, I think it is not fair to trash a proof just because of that.
If you can use exactly the same proof technique to arrive at a contradiction (e.g., by showing that P = NP), then you know that there is something wrong with the proof. But that is different from trashing the proof simply because the author is unable to explain why the proof doesn’t work for 2SAT or XOR-SAT.
Comment #191 August 12th, 2010 at 3:41 am
I actually don’t understand how the proof works (in detail). However, it’s so exciting to follow all the discussions. Fantastic!
One concern (maybe by Scott?) is why the proof doesn’t work for 2-SAT. (I noticed that Vinay recently tried to explain why.) Now, assume that the proof would actually work for 2-SAT implying 2-SAT not in P.
What consequences this would have for theoretical CS? (Remember Russell’s paradox) Would this also change your life dramatically, Scott?
Comment #192 August 12th, 2010 at 4:06 am
#192
“One concern (maybe by Scott?) is why the proof doesn’t work for 2-SAT. (I noticed that Vinay recently tried to explain why.) Now, assume that the proof would actually work for 2-SAT implying 2-SAT not in P.”
If the proof “works” for 2-SAT, then that proves 2-SAT is not in P. But, 2-SAT is known to be in P (there’s a polynomial time algorithm for computing 2-SAT). Therefore, the proof leads to a contradiction, which means the proof is flawed.
Comment #193 August 12th, 2010 at 4:18 am
@Marc: Most likely, this would be the fact. What I mean however is -as my assumption is that the proof is correct- whether there is the possibility that P does not exist (akin to Russell’s paradox), whatever this would further imply…
Comment #194 August 12th, 2010 at 4:27 am
@Tino: There are a class of problems which can be solved in polynomial time. Given this, I don’t get what you mean by “the possibility that P does not exist.” As far as implications go, if P did not exist, then there would be no problems that would be solvable in polynomial time, which would make computers pretty impractical for any meaningful computation. Even addition would be exponential in the number of bits, because the existence of a polynomial-time add operation would imply the existence of P.
I guess I’m not sure where you’re going with this.
Comment #195 August 12th, 2010 at 5:01 am
Reply To: Javaid Aslam Says: Comment #189 August 11th, 2010 at 10:52 pm: Would somebody like to honestly comment—had this been a proof of P==NP, would Deolalikar still get so much of attention from so many high profile academicians, in such a short time?
A P==NP claim would have got even more high profile attention than the PNP claim, because it would have led to umpteen number of publications and trillion-dollar patents for new polynomial-time algorithms, a literal gold rush in the field of algorithm design.
Not that there isn’t any scope for publications and patents after PNP. If the claim is upheld, we should probably expect updated versions of encryption standards and public key mechanisms not based on factoring.
Comment #196 August 12th, 2010 at 5:02 am
A: “What will happen if pigs fly?”
B: “Pigs DON’T fly.”
A: “Yes, but what if they did?”
B: “They don’t.”
A: “I know they don’t, but what if they did? Would it be a paradox? Would it mean there are no horses?”
B: “There are horses. If there were no horses then we couldn’t drink water.”
C: “????!”
Comment #197 August 12th, 2010 at 5:33 am
D: “C rocks. That was a hilarious summary of a hilarious exchange.”
Comment #198 August 12th, 2010 at 10:53 am
@qk and @Dave
Thanks a ton for answering my silly questions.
Rama Iyer
Comment #199 August 12th, 2010 at 1:04 pm
I am not an expert on this problem, but a superficial reading of the introduction seems to indicate that the whole theory only applies to k-SAT instances, where k >= 9. That means, it says nothing about 2-SAT. For that matter, it only says something about 3-SAT because all of NP reduces to 3-SAT.
Comment #200 August 12th, 2010 at 2:54 pm
@C
You are making two assumptions:
You can recognize a pig, and understand what is “flying”.
Comment #201 August 12th, 2010 at 8:58 pm
Reminds me of my own failed proof that P does not equal NP. My main result was that N cannot equal 1, but as the critics pointed out, I had overlooked the possibility that P equals 0.
Comment #202 August 13th, 2010 at 4:15 am
Frankly, the proof does not interest me much since its a proof of what we wont be able to do. It is better not to be accepted; if it is accepted I believe that people seeking challenges in this area will stop working hard and loose their motivation. It is better scientists to work on this problem when the byproducts, which will come out from these challenges, considered.
Also, I seriously condemn Turkish academic society for turning Turkish higher education sytem into a crap and corrupt environment, consisting of only vomiting the information you memorized in lectures into paper. Is there any one aware of this from Turkish math and CS scientists.
Comment #203 August 13th, 2010 at 6:24 am
Ahmet:
Frankly, the proof does not interest me much since its a proof of what we wont be able to do. It is better not to be accepted; if it is accepted I believe that people seeking challenges in this area will stop working hard and loose their motivation.
I completely agree! Likewise, it doesn’t interest me much when people tell me I don’t have wings—their negativity discourages me from jumping off tall buildings.
Comment #204 August 13th, 2010 at 7:30 am
Such proof would have to cover all classes of approaches … like continuous global optimization.
For example in 3SAT problem we have to valuate variables to fulfill all alternatives of triples of these variables or their negations – look that
(x OR y) can be changed into optimizing
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
and analogously seven terms for alternative of three variables. Finding global minimum of sum of such polynomials for all terms, would solve our problem. (from www .scienceforums.net/topic/49246-four-dimensional-understanding-of-quantum-computers/ )
It’s going out of standard combinatorial techniques to continuous world using gradient methods, local minims removing methods, evolutionary algorithms … it’s completely different realm: numerical analysis.
Such proof could work on concrete valuations, but here we work between them.
Does/can it cover also continuous approaches?
Comment #205 August 13th, 2010 at 3:07 pm
Ahmet, not only is that a bad reason, as Scott pointed out, but it is also missing part of the picture.
There are certain things that P != NP would make us much more likely to be able to do. They say one man’s trash is another’s treasure. In algorithms and complexity/crypto, one man’s difficulty is another’s success…
Comment #206 August 14th, 2010 at 12:12 am
@Scott:
“I completely agree! Likewise, it doesn’t interest me much when people tell me I don’t have wings—their negativity discourages me from jumping off tall buildings.”
Very nice way of saying “Pigs cannot fly” == “P=NP”
Comment #207 August 20th, 2010 at 12:00 am
Check out the P versus NP poll http://www.cs.umd.edu/~gasarch/papers/poll.pdf
2.2 How Will it Be Resolved?
1. 61 thought P6=NP.
2. 9 thought P=NP.
3. 4 thought that it is independent. While no particular axiom system was mentioned, I assume
they think it is independent of ZFC.
4. 3 just stated that it is NOT independent of Primitive Recursive Arithmetic.
5. 1 said it would depend on the model.
6. 22 offered no opinion.
Stephen Cook selected VD’s proof based on bio not bcoz of VD’s P==NP or P !=NP convictions.