The ethics of scientific betting
Throughout the day, Dick Lipton’s blog has hosted a phenomenal discussion of Vinay Deolalikar’s attempted proof of P≠NP (of which a new draft appeared as this blog entry was going to press). As of this writing, the discussion seems to have led to the following two conclusions:
- Deolalikar deserves our gratitude; he did a wonderful thing by bringing the TCS community together, in “Stone Soup” fashion, to talk about the P vs. NP problem, and also to stimulate public interest in this fascinating problem.
- My $200,000 is safe.
See in particular this magisterial summary by Terry Tao.
For those of you who just arrived from Mars, I’d recommend starting with a BBC News piece by Victoria Gill, which by the standards of articles about P vs. NP in major news outlets, bears an amazingly close relation to reality. Indeed, the only thing about the article that I disagreed with was the headline: “Million dollar maths puzzle sparks row.” It’s not a row, a spat, or even a squabble: at most it’s a friendly scientific disagreement among friends.
As many others have already said, and as the BBC News piece hints at, the clearest reason for skepticism is (basically) that Deolalikar hasn’t convincingly explained why his approach doesn’t also prove problems are hard that are already known to be easy. This is the simplest sanity check for any attempted proof of P≠NP: if you’re showing that an NP-complete problem like 3SAT is not in P, then your proof had better fail for related problems like 2SAT and XOR-SAT, which are known to be in P. Everyone agrees that, if Deolalikar can’t answer this objection, the proof is toast.Unfortunately, Deolalikar has responded to pointed questions about this issue with vague promises to address it in a later draft (together with worries that the manuscript is already too long!). This doesn’t inspire confidence: if one had really proved P≠NP, one should be able to explain immediately why the proof fails for XOR-SAT.This is far from the only problem with the writeup, but it’s a good example of the sort of basic question that Deolalikar needs to answer and hasn’t.
I feel incredible gratitude that Terry Tao, Timothy Gowers, Russell Impagliazzo, Avi Wigderson, Dick Lipton, Cris Moore, Ryan Williams, and other heavy-hitters of the math and CS worlds are hot on the case, and will quickly converge on what (if anything) is interesting and worthy of further study in Deolalikar’s writeup. What that means is that those of us trying to enjoy our “summer vacations” are free to debate other issues raised in the past few days—issues that don’t involve quite so much, y’know, actual thinking.And thus I’d like to propose a blog-roundtable about the following question:
Under what circumstances, if any, is it desirable to bet publicly on scientific questions?
The responses to my $200,000 offer made it obvious that people I like and respect have wildly different views on the above question.
On one side, Bayesians and economic rationalists of all stripes seemed ecstatic. The economist James Miller wrote:
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.
Several complexity theorists also wrote in privately to express their gratitude:
dear scott, have you heard? there is a P≠NP proof! what do you think of it? please let me know! just kidding. actually, this email is to thank you. my emailbox has been flooded with emails like the above lines, and thanks to your blog, i can now reply by mentioning your blog posting (the “I’ve literally bet my house on it” one—which nonetheless may be most remembered for being the only correct use of “literally” on the internet in the past 5-10 years).
On the other side, one distinguished colleague warned that my bet might hurt the image of theoretical computer science, by focusing attention on superficial snap-judgments rather than the technical evaluation of proofs. On this view, it’s my professional duty to make only scientific arguments in public: I should keep any personal guesses about a proof’s “probability of correctness” to myself. Sure, if I can pinpoint the fatal flaw in Deolalikar’s paper, I should say so. But if I can’t, I should just grin and bear it, even if journalists brush aside the experts’ boring, hard-to-explain technical reservations, and write article after cringe-inducing article exclaiming that “P≠NP HAS (APPARENTLY) BEEN PROVED!!!”
A different criticism—one that I confess took me by surprise—was that my $200,000 offer was “nasty” and “elitist,” something that eats disabled orphans for breakfast. On reflection, though, I think I understand where this was coming from. I felt like I was offering Deolalikar a damn sweet deal: he gets 200 grand if he’s right, and pays zilch if he’s wrong. However, the act of offering those odds might be interpreted as a perpetual “vote of no confidence” in Deolalikar’s personal ability to prove P≠NP.
By analogy, it would be reprehensible if I offered $200,000 to any member of a particular race or gender who proved P≠NP, with the implication being that I didn’t think that race or gender was up to the challenge. (And it would remain reprehensible, regardless of whether I eventually had to pay.) Of course, it’s relevant that that’s nothing like what I did: instead, spurred on by a barrage of emails, I spent a sleepless night with Deolalikar’s manuscript, weighed what I understood of his arguments on one hand and what I knew of the titanic obstacles to proving P≠NP on the other, and (may Merlin help me) cast a prediction accordingly.
Nevertheless, to deal with the “nastiness” issue, I’ve decided to clarify that my $200,000 offer remains in effect until January 1, 2019. That gives Deolalikar a couple more years to finish his current proof (plus more years for the journal refereeing and Clay prize processes), but it also makes clear that my bet is against a specific claim to have proved P≠NP, not against a person for all eternity.
(To answer the other question people kept asking me: no, my offer doesn’t extend to any potential P≠NP prover, much less to the other Clay Problems! I’m hopeful that, within my lifetime, theoretical computer science will have advanced to the point where statements like P≠NP can be proved, and I’ll of course be elated, but not so catatonic as to make giving up my house seem completely immaterial by comparison.)
So: is it the duty of a scientist to express, in public and as a scientist, only what he or she can articulate reasons for? Or is it sometimes appropriate or even desirable for scientists to go beyond what they can verbalize, using such mechanisms as bets? Now it’s your turn to weigh in! I’ll be following the discussion by iPhone during a road trip through northern Israel, to the enormous annoyance of my traveling companions.
Update (8/12): I was hoping for some enlightening discussion about the ethics of scientific betting in general, not more comments on the real or imagined motives behind my bet. However, the actual comments I woke up to have convinced me that the critics of my bet were right. In principle, the bet seemed like a good way to answer the flood of queries about Deolalikar’s paper, and then get back to enjoying my trip. In practice, however, the way people respond to the bet depends entirely on what they think about my motives. If you don’t care about my motives, or consider them benign, then the bet probably provided a useful piece of information or (if you already knew the information) a useful corrective to hype. If, on the other hand, you think I’m arrogant, a media whore, etc., then the bet served no purpose except to confirm your beliefs. Given the number of commenters on this blog who wish to ascribe the worst motives to me, it seems like the bet was counterproductive.PS. Arrogant I can see, but media whore? Really? Is it relevant that curious, well-meaning folks were pestering me to react to this announcement, that they clearly wouldn’t stop until I did, and that I was just trying to answer them while otherwise getting as little involved as I reasonably could?PPS. I’ve said this before, but let me say it again: I am unbelievably grateful to the “rapid response team” of mathematicians and computer scientists who dropped whatever else they were doing to delve into Deolalikar’s paper, and to report what they found on Lipton’s blog and elsewhere. Precisely because of their excellent work, there seemed to me to be little point in canceling my travel plans in order to try and duplicate their efforts.
Follow
Comment #1 August 11th, 2010 at 9:28 pm
@Scott
In response to the “hasn’t convincingly explained why his approach doesn’t also prove problems are hard that are already known to be easy”:
Is it trivial to assume that a successful proof of P≠NP will be of the kind where the NP problems are explicitly shown to be hard? I was under the impression that it was possible, and that in fact Vinay’s proof was an example of, to prove it through a completely indirect way that made no explicit reference to the hardness of NP-complete problems. i.e. show that P=NP implies some other independent result of TCS that we already know to be false/different/etc. (which is what I thought he did). I’ll admit that I haven’t read his paper, nor have the experience in the field for it to be worth bothering, so maybe I’m just misinformed, but perhaps the question is unanswered because it isn’t really applicable to his technique? (not that this would alleviate the potential for incorrectness)
Comment #2 August 11th, 2010 at 9:36 pm
Thought experiment: Suppose I announced the following
“If Scott Aaronson wins the Millennium Prize for solving P vs NP I will give him 200,000 US Dollars. I feel that my money is very safe.”
Would people consider that “nasty” or just an innocent Bayesian expression of belief?
Comment #3 August 11th, 2010 at 9:36 pm
I’m loving the drama you’ve created around this issue, and I’ll be eating popcorn watching it unfold 😀 Deolalikar, being certain of his proof, should be happy with your unexpected boost to the prize money he’s confident he’ll get, so there’s nothing nasty about your bet.
Comment #4 August 11th, 2010 at 9:39 pm
Scott, you are such an attention seeker—in a way you are the antithesis of Grisha Perelman. Here is a man Deolalikar, who is probably spending sleepless nights, and instead of helping with the effort of checking or even commenting on the manuscript, you made that aweful bet. The “sweet deal” angle falls flat on its face because there is almost no plausible reason for you to give him a sweet deal, whereas knowing you, there is a good reason that you are offering this money based on your impression of either the manuscript, the person, or the level of his past work. Each case leads to a stinky hypothesis. The issue is also not that scientists shouldn’t verbalize what they can’t prove etc. The issue is of muddying the waters of the whole affair further. There was no need for it. If the proof fails, there is already a lot of media coverage about it, which won’t turn out to be good. But being attention seeking and all made it worse.
Comment #5 August 11th, 2010 at 9:40 pm
To clarify:
Is he addressing the problem without reference to the \emph{members} of NP?
If anything, as an uneducated observer, I’d wager that when/if we get a successful proof of P≠NP that it will be of this form (not proving any specific problems are hard directly). It just seems like typical nature BS to give you a proof of something really hard that doesn’t actually give away the workings of the issue that you really care about (think nonconstructive proofs). Yes I realize that P≠NP instantly proves NP-complete problems are harder than P, but the proof doesn’t have to actually show how to directly prove that a problem is hard. If it is proved in such a way, all of the NP-incomplete problems would still be elusive. And like I said, I might wager $200K in Monopoly that Nature’s tendency toward elusiveness will lead to this type of result.
Comment #6 August 11th, 2010 at 9:43 pm
I thought the bet post was great information, and would like to see more such bets offered to provide instantly credible offsets to credulous news coverage.
However, it might have been better if the bet was smaller, so we could be more confident that you wouldn’t try to get out of it in the event of a loss.
Comment #7 August 11th, 2010 at 9:46 pm
@Bob:
Context matters. Scott’s already so well-known and you are probably not as well known, that the general impression would quickly be that you are just joking. On the other hand, if you claimed to have finished running the Boston marathon, and Lance Armstrong bet 200k that you probably didn’t finish, then the general impression is quite different. In the latter case, people would surely reprimand Armstrong for being such a downer. And it doesn’t matter even if you actually didn’t finish the marathon. When Scott made the bet, he made it look like he hadn’t even read the manuscript. This led most people to believe that he was so sure Deolalikar couldn’t prove it that he didn’t even have to read the manuscript. Scott didn’t even mention that he had consulted others who had read it and then made up his mind. So it appeared that Scott had made the bet just after simply hearing that some person VD from HP had claimed to prove PNP. This cast Scott’s bet in a totally different light. As I said, context and perception matters; correctness is not enough in human-human communication.
Comment #8 August 11th, 2010 at 9:49 pm
@Carl: the bet itself was great fun, but the way it was presented was nasty.
Comment #9 August 11th, 2010 at 9:52 pm
@Justin: The proof uses statistical properties of solutions of random k-SAT. It turns out that the solutions of random k-XORSAT have similar statistical properties to those of random k-SAT. But random k-XORSAT is known to be in P whilst random k-SAT is NP-Complete.
Hence if these statistical properties are the only things the proof depends on, it would seem that the same argument would also prove that random k-XORSAT is not in P (something which is known to be false). Hence something would have to be wrong with the argument.
However, it is not yet completely clear if the argument cannot distinguish random k-XORSAT from random k-SAT (partly due to some ambiguity in the manuscript). I believe this is one of the issues Deolalikar is trying to address in his revisions as he mentions it briefly in his latest update (but not enough to satisfy the experts).
I am not an expert, this is just my summary of the discussion over at Lipton’s blog.
Comment #10 August 11th, 2010 at 9:58 pm
It’s a clever way to avoid thousands
of email-questions about the paper.
I don’t see anything nasty about it.
But in case the proof is correct,
i would donate $100 to the
“save Scott Aaronson’s house”-
foundation if you could give
a short answer to comment#26 in your
post “My diavlog with Anthony Aguirre”
a “sorry, the idea is stupid” would be enough 🙂
Comment #11 August 11th, 2010 at 10:07 pm
I don’t generally think that scientific betting is unethical, just that the bet you have made is. Bets are generally consensual and equivalent (think Hawking’s bets about black holes). Let’s say the conditions for the payout are met. Knowing that the payout of the bet presents a significant hardship most people would not accept it; accepting it would make you look greedy and such in some people’s eyes. However, refusing it also has social consequences. You put him in a difficult spot that he did not ask to be in. Were I in those shoes I would decline the offer or if they are insistent have the money donated to a charity.
Comment #12 August 11th, 2010 at 10:09 pm
@Quantum Tennis Referee:
I actually agree with you, I think you captured well one of the reasons people might consider the bet “not nice.”
Comment #13 August 11th, 2010 at 10:14 pm
@Bob
Ah okay. Though isn’t that irrelevant since the proof just says P=NP –> random k-SAT has statistical properties A whereas we know random k-SAT has statistical properties B? I don’t see why (if its really as I have just described) that whether or not random k-XORSAT has statistical properties A,B,C,D,…,X,Y,Z,… makes any difference. As I’ve been lead to believe, the proof doesn’t use the stat properties of ran k-SAT to show that it is outside of P (if it did I would see the issue) but rather to point to a contradiction in the corollaries of P=NP.
Comment #14 August 11th, 2010 at 10:31 pm
Writing “Indians can’t prove anything about P vs NP” on your blog would be nasty because it’s derogatory *without being accurate*. But if you pick a reference class for which your generalization is accurate, like “violators of the 10 crackpot indicators”, then it’s not nasty.
When you bet your money, you’re not being nasty because you’re clearly making a good-faith attempt at accuracy.
So I think any publicly available new proof should get a prediction market about its validity. Then everyone with a coherent belief state gets non-negative expected utility — including the author of the paper — and the accurate information that gets broadcast makes the exercise positive-sum.
Scott should have been able to simply place a sell order for $200,000 worth of contracts at a price corresponding to 1% probability.
– If the early market consensus for the proof’s accuracy is higher, say 10%, then anyone can buy Scott’s contracts and flip them for instant 9% profit, including Deolalikar himself.
– If the market consensus supports Scott’s 1% probability estimate, then there’s no insult to Deolalikar in believing the same thing as the market under limited uncertainty.
I’ve suggested a market for Deolalikar’s proof on the Intrade forum: http://bb.intrade.com/intradeForum/posts/list/4586.page
Comment #15 August 11th, 2010 at 10:49 pm
Guys, you’re missing the genius behind Scott’s bet.
He has essentially managed to attach his name to the Deolalikar publicity and media frenzy while doing roughly 0% of the work relative to folks like Lipton or the others who are busy making refutations of the proof.
Every article citing this proposed proof now carries Scott’s name, mentioning his $200,000 bet, and his name recognition has skyrocketed. Hell, I didn’t know who he was until I started reading these articles, now here I am, reading his blog.
Many of us were skeptical about a claim to prove P=NP emerging suddenly out of nowhere by a single researcher at HP labs. But only Scott found a way to turn this into a fabulous exercise in PR. His readership must have increased tenfold.
Well played, Scott, well played.
Comment #16 August 11th, 2010 at 10:49 pm
@Justin
“the proof doesn’t use the stat properties of ran k-SAT to show that it is outside of P (if it did I would see the issue) but rather to point to a contradiction in the corollaries of P=NP.”
Well I’ve been led to believe this is EXACTLY what the proof does. Perhaps someone else could chime in if this is wrong.
Comment #17 August 11th, 2010 at 10:54 pm
If i try i can see a pattern in P = NP and P != NP attempts.
In my limited experience, in P = NP there’s typically a given family of inputs that the polynomial time algorithm misclassifies – e.g. that graph G is a clique, when it’s not.
In P != NP apparently there’s usually a given problem that the proof misclassifies – e.g. that 2SAT is not in P.
One side asks for an algorithm, the other for a proof. One side has to include/exclude a set of input families, the other has to include/exclude a set of problems.
I’m oversimplifying, but the two sides, from the far off position that i sit, seem to be… equally difficult. Is this something that is typical in other open problems? One side should be impossible and the other one should be doable. It’s like the problem of proving P = NP reduces to the problem of proving P != NP, and vice-versa. Geez.
Comment #18 August 11th, 2010 at 11:24 pm
@Terrence:
I didn’t know that Scott was as much of a media attention seeker as other silly celebrities on the 10 o’clock news. It only takes the intelligence of such a silly celebrity to cash in on somebody else’s parade.
@Liron:
I know Scott and I am somewhat confident that he did not intend to be nasty. But his bet could be perceived as nasty without it actually being nasty. It all depends on the context.
Comment #19 August 11th, 2010 at 11:49 pm
“He has essentially managed to attach his name to the Deolalikar publicity and media frenzy while doing roughly 0% of the work relative to folks like Lipton or the others who are busy making refutations of the proof.”
Exactly, Scott’s bet was all about grabbing attention for himself, and had nothing to do with either science or Bayesianism. “Well played” for sure. Patrascu could never have managed it.
Scott, if you want to be take the crown as TCS clown, you should up the stakes. Why not bet $200,000 that Lipton will never prove P != NP?
Comment #20 August 12th, 2010 at 12:01 am
While I’m flattered that Scott apparently thinks my entire home page consists of nothing but magisterial commentary, I presume the link that was intended was in fact http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4885
Comment #21 August 12th, 2010 at 12:23 am
@Justin 12: My understanding is the question comes down to something like, “why can’t one take the existing proof and do a search-and-replace from k-sat to k-xorsat (or another analogous problem known to be in P but with similar characteristics)?” If the proof allows one to do this, then the proof cannot be valid.
Comment #22 August 12th, 2010 at 1:16 am
@Tao:
I was wondering about that, thanks for the update.
I read that comment and I found it very pleasant and useful. But I don’t think magisterial is the right word.
Geez Scott, what’s happened to your choice of words lately????
Comment #23 August 12th, 2010 at 1:20 am
Tao #20: Thanks, fixed! Although I think “magisterial” was also pretty accurate with the original link. 😉
Comment #24 August 12th, 2010 at 1:35 am
Juicisian (#22): You had me worried for a minute. But
mag·is·te·ri·al (m j -stîr – l). adj. 1. a. Of, relating to, or characteristic of a master or teacher; authoritative
Yeah, that’s what I meant. 🙂
Comment #25 August 12th, 2010 at 1:42 am
Bob (#2):
Thought experiment: Suppose I announced the following
“If Scott Aaronson wins the Millennium Prize for solving P vs NP I will give him 200,000 US Dollars. I feel that my money is very safe.”
Would people consider that “nasty” or just an innocent Bayesian expression of belief?
My post explicitly addressed that issue, setting the terms of the bet to clarify that it’s a comment about a specific manuscript, not a person.
On the other hand, I can say that personally, I’d have no problem whatsoever with your making such a bet against me, even though I wouldn’t expect to collect on it.
Comment #26 August 12th, 2010 at 2:15 am
I think that it is irresponsible for scientists to use their reputations to put out cheap talk in favor of positions that they are not able or willing to argue for, as doing so dramatically lowers the caliber of public discourse. However, putting out expensive talk, taking risks, in order to transfer their complex but relevant knowledge into the public discourse, is extremely laudable, and in fact, it’s probably something that I should consider having SIAI fund a prize for if I could think of a good formulation. It all boils down to the impact of a given norm on the epistemic quality of the relevant social environment.
Comment #27 August 12th, 2010 at 2:17 am
To add to Bob’s thought experiment: does making a bet like that make it more or less probable that Scott will solve P vs NP ? 😛
Comment #28 August 12th, 2010 at 2:21 am
I apologize for using the word “nasty” which apparently has a stronger meaning than what I wanted to say.
When I first read Scott’s post and commented on it, it looked to me that the bet is a rhetoric device to express how tiny tiny probability he assigns to Vinay being right in a deamining way. But later it did not look so bad to me and, in fact, I myself will be quite pleased if Scott will offer to pay me additional 20% for an unlikely prize I will get, say on my perfect English or on some other matters.
I do not think it is the duty of a scientist to express his opinion on a scientific matter without looking at it while being on vecation in Israel. Everything always can wait for a few days. (I have to remember it myself.)
On the more serious matters: Suppose we set a betting market for the question if factoring is in P. Prominent mathematicians will put their money (and houses) where their mouth is. Will it give us clearer view about the answer? Most probably not.
Does theoretical economists suggest otherwise? Well, there are some insights related to what is called “rational expectation” that may suggest that the betting market will lead to signals of individuals being aggregated (somehow) to the correct answer. It is a nice excercise to try to figure out why this will not apply in our case (and actually does not apply in various cases of economic interest). So I think Jason was simply wrong. I do not think that betting about scientific matters will advance science. On the contrary.
What about scientists discussing scientific matters on blogs?
Another interesting issue: It seems that older people have more patience than young people. Why is that? (From a rational point of view they should be less patient, no?)
Comment #29 August 12th, 2010 at 2:33 am
Honestly, Scott would benefit from such a bet against him, as it would enable him to a) possibly get $200K, and b) direct his future efforts to something more likely to succeed in response to the info you would be giving him about your beliefs and confidence, assuming that he respected your reasoning (and he would have to respect it if you routinely made such bets and were always right, or at least hadn’t been ruined by them). The rate at which knowledge evolved would probably benefit greatly.
Comment #30 August 12th, 2010 at 2:35 am
Scott, I personally didn’t like the tone in which your first blog. I had high regards for you and your work but I think the manner in which you undermined someone’s effort shows the kind of respect that you give to others work. Infact, many people were unhappy about your prize offer blog on coffee table.
As rightly pointed by some great mathematician, you could have been more polite and encourage more people to try this difficult problem.
Alas, you were laughing on it.
;(
Comment #31 August 12th, 2010 at 2:50 am
I’ve spent a few minutes here attempting to see the situation from the “nasty” perspective, but I seem unable. It appears to me that you have to do quite a lot of inferring about Scott’s supposed unspoken meaning to turn it into something rude or cruel.
@Quantum Tennis Referee (#7):
RE: the Boston Marathon/Lance Armstrong analogy — That just feels like quite a different situation than this. A person finishing the Boston Marathon and a person solving P vs NP have quite different occurrence frequencies… If you make a genuine, serious attempt at P vs NP (and especially if you “announce” it publicly!), I don’t think you fall in the category of “not well known” any longer.
Comment #32 August 12th, 2010 at 3:33 am
First, I do not think your $200K Aaronson-prize post was nasty. Attention seeking, maybe, but not nasty. Reading your post carefully, it is clear that the Aaronson-prize offer was for Deolalikar’s specific proof attempt, not for Deolalikar in perpetuity. As such, it is just a device of expressing your strong belief about Deolalikar’s paper, without providing justification.
Second, here’s a point nobody expressed earlier. I think your post was a great service to the TCS community. I was just about to drop everything, and spend a day (or more) reading Deolalikar’s paper. But then I saw your post, and decided against it. Your $200K offer was much more convincing than indications of possible gaps in the proof that have surfaced by then. Impagliazzo has forcefully raised the collective “waste of time” problem at http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p≠np/#comment-4918. Well, you found the perfect solution to the problem, even before Russell posted it. Imagine how many hundreds of hours of computer scientists’ time your post has saved!
Comment #33 August 12th, 2010 at 3:52 am
Toshiaki (#11): Obviously, Deolalikar would be more than welcome to donate the money to any charity of his choice, or have me donate it for him. Or just turn it down, like Perelman. For this reason, I don’t understand the “nonconsensual” argument.
Comment #34 August 12th, 2010 at 4:02 am
I posted something similar on the “Putting money where …” discussion and realized after reading this discussion that this discussion is more appropriate.
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.”
Has anyone used the proof to show that 2SAT or XOR-SAT is in NP? It doesn’t have to be rigorous – even a reasonably plausible showing that the proof will work for 2SAT or XOR-SAT should be sufficient to raise doubts. However, if that has not been done, then trashing the proof simply because the author doesn’t have a “clear and convincing” explanation of why it won’t work for 2SAT or XOR-SAT is not, in my opinion, fair.
Of course, if the author can show why the proof doesn’t work in situations where 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 if previous attempts to explain why the proof does not work for 2SAT, XOR-SAT have exposed flaws in the proof, 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.
Comment #35 August 12th, 2010 at 4:38 am
Buzzinga: In a formal sense, you’re right. But given the reality of limited time, these sorts of sanity checks are an accepted way of convincing people that your claimed proof is worth reading. The responsibility is Deolalikar’s to show that the proof passes them, not other people’s to show it doesn’t. Having said that, if you visit Lipton’s blog, you’ll find a huge number of pointed, specific comments strongly suggesting that Deolalikar’s proof doesn’t pass these tests. I hesitate to say they’ve “proved” it, since the proof itself is a moving target: in response to any criticism, Deolalikar seems to say “yes, of course, I’ll deal with that in a later draft.”
Comment #36 August 12th, 2010 at 5:11 am
Fair enough. I agree the burden is on the author to show that the proof passes the “smell test” especially if the author wants people to go over a 100+ page document.
I also understand Deolalikar’s desire to distribute the proof early (even if it is half-baked) and work out the wrinkles later.
I’m sure grad students and post-docs are busy trying to find holes in the proof. For them this kind of stuff is important enough (or should be in my opinion) to drop whatever they are doing (which is usually not much).
Comment #37 August 12th, 2010 at 5:11 am
I think there are basically two issues: When to bet and how to bet. I’ll start with the latter.
If the intention of the bet is to add credibility to ones opinion (I guess this applies here, this is not the kind of bet where Scott could gain money), one should make sure that there is no way out of the bet. I don’t think this is the case here. I don’t know how legally binding an announcement on a blog is, but I guess little was done to ensure that the case is tight. Moreover, if Deolalikar actually gets a million bucks and is known in the world as the person who solved a problem of such a caliber, I doubt Deolalikar could cash in without appearing to be a jerk. It would be more credible to announce that the money would go to a charity that can cure suffering more important than an assistant professor at MIT losing his house. Such a charity would check in. So I think the bet was more of a rethorical device. Whether this was the original intention, I do not know, but one could have avoided this impression.
On the question of when to make such a bet, I think the scientific community gains little from it. Such a bet might help one to reveal “private knowledge”, but in mathematics there is little such knowledge. Either you have a proof or you may have at most some heuristics which are likely to be available publicly. Here I side with Gil Kalai, prediction markets for scientific problems seem to be of little use. I do think however that there are cases where scientists have a reason to put their money where their mouth is. Suppose an economist is known for being both brilliant and partisan. She announces that some policy proposal from the other side would have some verifiable, horrible consequences. In this case, betting on the consequences can credibly signal that the economist supports an opinion because she actually believes it and not because she is partisan.
Comment #38 August 12th, 2010 at 5:24 am
@Bob
How many scientists from MIT does it take to solve a millenium prize problem?
200,000!
Comment #39 August 12th, 2010 at 5:32 am
Scott,
I fully agree with James Miller. But I was surprised seeing you betting. If I remember well, you once said something close to “I can’t bet on whether we will see a quantum computer soon: I just don’t know!”.
Having some experience with “scientific” betting, let me explain why I disagree with the latter comment. Of course I don’t know better than you about QC. But just because I know you don’t know, this is enough information for me to bet!
I wonder whether you used the same trick when your read Vinay Deolalikar’s attempted proof of P≠NP. It seems that you didn’t know for sure if the proof was false or not. But wasn’t your own state of ignorance enough information for betting?
Comment #40 August 12th, 2010 at 5:32 am
IMHO, what you have done with your bet is similar to the distinction between “saying” and “showing” in Wittgenstein’s philosophy. You showed your opinion in strong way and this couldn’t be achieved using arguments. This ability to go over what can be said in a humorous way is one of attributes that make you different and relatively popular.
Comment #41 August 12th, 2010 at 5:46 am
Michael #37: I actually agree with you that there’s very little private knowledge in mathematics—or at least, very little knowledge that can’t be articulated publically given enough time and effort. For that reason, I wouldn’t support betting on proofs except in unusual situations. This is an unusual situation.
Comment #42 August 12th, 2010 at 5:55 am
Jiav #39: I knew someone would make a quantum computing analogy sooner or later! 🙂 One could ask: why didn’t I similarly announce a bet against D-Wave? In my mind, the crucial distinction is this: any bet against D-Wave could easily degenerate into acrimonious debate about the exact conditions of the bet. With a claimed mathematical proof, things are much more clear-cut.
Comment #43 August 12th, 2010 at 5:58 am
Scott, I think you are messing up your comments, to the point of being contradictory. On one side (in the main text) you say:
“However, the act of offering those odds might be interpreted as a perpetual “vote of no confidence” in Deolalikar’s personal ability to prove P≠NP.”
and in a comment you post
“My post explicitly addressed that issue, setting the terms of the bet to clarify that it’s a comment about a specific manuscript, not a person.”
Comment #44 August 12th, 2010 at 6:13 am
aleh, did you read a few sentences further in the post? Y’know, to the part where I talk about setting the terms of the bet so that it WON’T be MISinterpreted that way?
Comment #45 August 12th, 2010 at 6:36 am
Yes, sorry, actually I had read everything but probably it was myself who had misinterpreted the first sentenced I quoted, opposed to the previous (non-quoted) sentence where you say what you felt, you know about the damn sweet deal.
BTW, I also think your money is safe, even with the 9-year extension… 🙂
Comment #46 August 12th, 2010 at 6:41 am
OK, thanks!
Comment #47 August 12th, 2010 at 6:52 am
Quantum Tennis Referee (#4): While (like most of us) I can’t even hope to approach Perelman’s brilliance, I’m perfectly happy not to share his personality. Growing up, the mathematicians and scientists I admired most were never those who withdrew from the world, but rather those (like Bertrand Russell and Carl Sagan) who tried as hard as possible to change it.
Comment #48 August 12th, 2010 at 7:22 am
http://www.newyorker.com/archive/2006/08/28/060828fa_fact2
Comment #49 August 12th, 2010 at 7:29 am
As I recall, Gil, you speak better English (albeit accented) than most of the undergrads did…
Comment #50 August 12th, 2010 at 7:54 am
Scott, any bets on “Will HP fire VD” by Jan 1, 2019 …
Comment #51 August 12th, 2010 at 8:09 am
My motto used to be “What would Grisha Perelman Do” WWGPD?
But now it’s quickly and unexpectedly been supplemented by “What would V. D. NOT Do” WWVDND? or how NOT to solve a milleniyum prize problem!
BTW when is the next Update? Can I download it with my next Windows Update? Will I be forced to restart my brain each time after I glance through an updated pdf, like I’m forced to restart my computer after a Windows update?
Comment #52 August 12th, 2010 at 8:11 am
The original post didn’t seem nasty to me at all, but now I suppose I can see why some people might see it that way. But I think that if the tone were changed, it wouldn’t come across that way at all. Compare it with this: “X uses techniques which I myself would never have had the audacity to pursue. I don’t yet understand his proof, but assuming it checks out, it will no doubt come to be seen as one of the great mathematical achievements in history. I would be honored to add my own gift of $200K to his prize money.” Same difference.
As a working mathematician, I’d be delighted if someone was willing to make even a much much smaller offer on my own work. Now if you want to argue that it’s a bit unseemly to start flashing money around, then sure. But otherwise I think the people who are objecting might be projecting as well.
Comment #53 August 12th, 2010 at 8:28 am
Scott, IMHO, Perelman did change the world in his own way. He did not accept those awards, an action that almost none of us would do, and it is similar to your $200k bet. He has made a strong statement. If it was not, we would not be still talking about it after this many years. I know that you will ask what is his statement? But we don’t understand it because we don’t understand his views. I think his action has moved some of us who understand it towards his ideas on how mathematical society should have been. 🙂
Comment #54 August 12th, 2010 at 8:46 am
If VD was with Microsoft instead of HP, the proof updates could be optionally downloaded with Windows update!
Comment #55 August 12th, 2010 at 8:59 am
I just thought the bet was a jokey way to say “I really don’t think this proof is going to hold up.” I completely failed to ascribe either arrogance or Bayesian rationality to it!
Comment #56 August 12th, 2010 at 9:16 am
How many jobs and opportunities were created due to this proof?
Comment #57 August 12th, 2010 at 9:43 am
“the actual comments I woke up to have convinced me that the critics of my bet were right.” [albeit for unexpected reasons, maybe]
I’m glad. Intuitions are important, but involving large sums of money does seem to steer the conversation wildly off target.
I hope your vacation has been sunny and relaxing! Thanks for taking a little time out of it to work on this.
Comment #58 August 12th, 2010 at 9:44 am
Why do academic papers with 1 author begin with “We show that”??
Comment #59 August 12th, 2010 at 10:12 am
I think your previous post would’ve gone over better with the masses had you added something similar to:
“I spent a sleepless night with Deolalikar’s manuscript, weighed what I understood of his arguments on one hand and what I knew of the titanic obstacles to proving P≠NP on the other, and (may Merlin help me) cast a prediction accordingly.”
Comment #60 August 12th, 2010 at 10:35 am
Since this is a post about the ethics of scientific betting, how is it ethical to change the terms of your bet after making it (and getting worldwide attention for it).
I’m sure you are thoughtful and have the best of intentions, but come on, a bet’s a bet.
Comment #61 August 12th, 2010 at 10:40 am
There is some precedence on the ‘net for this sort of proposition. During the leadup to Y2k (1997-2000) there were many rumors of cars that would not start on 1 Jan 00 [sic] due to y2k bugs in embedded chips in cars. Steve Burkett offered $100 to anyone who could prove that a starndard production car had such a problem. Others joined the challenge and by 1999 the fund had grown to $700. The history can be found in the USENET newsgroup comp.software.year-2000.
Even earlier, participants of the USENET newsgroup sci.physics.fusion which was created in response to the claims of Cold Fusion by Fleischman and Pons(1989) funded a trip (1992) by Tom Droege to investigate a laboratory that was making related questionable claims.
http://www.jstor.org/pss/689988
I would like to thank Scott for taking the risk. The wager played no small role in crystallizing the P =?= NP rapid reponse team.
–bks
Comment #62 August 12th, 2010 at 10:55 am
Corey Kosak (#60): I didn’t change the terms of the offer. My original offer contained the ambiguous phrase “his proof of P!=NP” — what exactly would I count as such a proof? — so in this post, I clarified it.
Maybe I could’ve gone to law school. 🙂
Comment #63 August 12th, 2010 at 10:56 am
“I’ve decided that my $200,000 offer will expire on January 1, 2019”
Trying to weasel out already are you? 🙂
On a more serious note I still can not see how the original post could be considered nasty. P vs NP is believed to be a very difficult problem so that Scott doesn’t believe Deolalikar had solved it is hardly an insult. Further, giving the mounting hype it was responsible for Scott to do something to dampen it.
As for the legal status of Scott’s offer I’d guess it is legally unenforceable. Usually promises with nothing given in return are not legally enforceable.
Comment #64 August 12th, 2010 at 10:58 am
Scott: one way to show everyone that you have decoupled your feelings towards the proof v. your feelings towards the prover is to completely focus your bet on the proof. (I’m not suggesting that you have any particular feelings towards the prover in this case.)
One way to do that is by making the following bet (there may be other, possibly better, ways to achieve this): I, Scott Aaronson, bet 200K that the current version of Deolalikar’s paper does not constitute a proof, and his approach will not result in a proof without major modifications and/or additional insights.
Comment #65 August 12th, 2010 at 11:00 am
Yisong (#59): In retrospect, you’re completely right! But there’s the rub: that I would (try to) READ the proof before making such an offer, I considered too obvious to be worth stating. I’d forgotten about so many people’s tendency to give everything I write the least charitable interpretation possible. 🙂
Comment #66 August 12th, 2010 at 11:07 am
For me, the bet was nasty and unnecessary. If you are a CT with a lot of experience, you should be able to express yourself with words, not bets. And maybe contribute to the discussions born around the D. work.
Otherwise, one is lead to think that Scott feels that the attempt made was so embarrassing (so plain wrong, made by a person without the needed experience/skills etc…) that he will not spend his time commenting on the proof. Just a bet of 200k….
Clearly, he has more important things to do…
Comment #67 August 12th, 2010 at 11:09 am
Buzzinga (#64): See, but if I did that, then people would again call me uncharitable, for not giving Deolalikar a chance to claim the prize by “fleshing out” his original writeup. If I’ve learned one thing since this story broke, it’s that I can’t win with everyone…
Comment #68 August 12th, 2010 at 11:24 am
Why are we talking only about Scotts’ ethics? Let us also question kindly the ethics or professionalism of Vinay D. Is his behavior professional? Is his paper written in a professional manner?
Let’s here you people.
Comment #69 August 12th, 2010 at 11:27 am
The point of this post is to muddy the waters further–otherwise there would be no need to suggest a concern with ethics. A crucial assertion in the original post has been omitted from the characterization of the bet: “I’m dead serious–and I can afford it as well as you’d think I can.”
The terms of the bet were changed in this post–so much for dead seriousness. Aside from that, the afterthought is a case of putting one’s mouth where one’s money isn’t–a pointed vote of no confidence.
Comment #70 August 12th, 2010 at 11:28 am
Johan (#63): Consideration can be tricky concept. I think Scott’s unilateral contract is enforceable unless there is a case with substantially the same fact pattern that holds otherwise. See the entry for a unilateral contract on Wikipedia: http://en.wikipedia.org/wiki/Contract#Bilateral_and_unilateral_contracts.
Comment #71 August 12th, 2010 at 11:33 am
I think you’ve got a sampling problem: the people who are offended are much more likely to chime in than those who aren’t. I also think you already know this.
I’m just chiming in to say that I think your bet was humorous, helpful, awesome, and totally unoffensive. I’d also like to thank you for your willingness to go out on a limb and not “keep any personal guesses about a proof’s “probability of correctness” to myself”.
Comment #72 August 12th, 2010 at 11:35 am
Don’t we suppose (ideally) that the scientist, seeking truth, doesn’t have an interest in what the truth turns out to be? And doesn’t betting complicate this?
Comment #73 August 12th, 2010 at 11:36 am
I think the questions behind your motives are mostly based on the fact that it is an, apparently, isolated event. Since there is no personal precedent (that I am aware of) for this action, the motives are difficult to discern. Therefore, my request for you is that you continue making such value bets on your beliefs so the rest of us can at least have something to compare this event to, and gain real some information from an expert. (Easy for me to say, it’s not my house!)
As to your “media whore” status, you have the deck stacked against you. I agree with your assessment that the BBC News piece is at the top of the mainstream media articles published on this topic, but unfortunately it only quotes you! Personally, I believe this to be coincidental, but to most it can only serve to undermine your (completely justified!) opinion.
Comment #74 August 12th, 2010 at 11:42 am
I believe there is sufficient momentum to sustain a polymath project to determine the motivation behind the bet.
Comment #75 August 12th, 2010 at 11:57 am
Let me (desparately) try to return to the enlightened discussion and answer my own excercise on why the idea that betting markets will give us clearer scientific picture on the world is incorrect.
In the economics setting of “rational expectations” there is an unknown state of the world on which agents have private information. The market prizes aggregate the private information in a subtle way and reveal the true state of the world.
The principal reason that this is not relevant to scientific questions is that a basic implicit assumption in all these models is that if all the private information of agents about the state of the world will be made public, this will suffice to determine the correct state of the world. (Say with extremely high probability). The behavior of agents in the market (or in other strategic situations) give a way for the private information to aggregate as if it was common knowledge.
But, of course, this is not relevant here. Even if we know the sincere private opinion of all scientists on a question like is factoring in P (and even their opinions about opinions of others, and whatever additional information that we want, and we can even give them time to reconsider their opinions based on pinions of others etc etc…) making this private information public is not sufficient (and usually does not help) to determine the “state of the world”.
This is the main reason why this teaching from theoretical economics do not apply. And indeed, this concern is relevant to various economics scenarios.
(I should add that even if private information is sufficient to determine the state of the world the conclusion that this will be revealed by the market, is rather problematic and depends on various additional factors.)
Comment #76 August 12th, 2010 at 11:57 am
Dear Scott,
You won your own bet, good job there!
Would you enlighten us as to what was the PROCESS behind your quick and correct judgment? Whereas the other Computer and Mathematics luminaries fell for it hook, line and sinker; Timothy Gowers, Gil Kalai, Ken Regan, Terence Tao (Fields medal), and Suresh Venkatasubramanian and Dick Lipton, all of ’em and the news outlets!
I’m sure its a P =? NP thing again! Your quick nondeterministic hunch about the wrongness of all the 100 pages was quickly verified as correct. But how did you do it, confidently risking your reputation like a smooth poker player?
Do you believe that a layperson, somebody not a top scientist can still solve a millenium problem? After all, Vinay Deolalikar working HP labs a top scientist, Phd from USC, and Bachelors from IIT!
Perfect marksmanship cowboy!
Comment #77 August 12th, 2010 at 11:58 am
I for one enjoyed the bet and it has brought in at least 1 new frequent viewer (added your blog to my reader). Betting on scientific breakthroughs brings an edge of excitement for both people in the research and outside viewers. As long as it is backed to some extent by healthy reasoning, not necessarily by any specific counter example, but at least explained. You definitely presented the bet in a way that I don’t think others could do quite so well.
In the end you can’t be held accountable for the media twisting the purpose and reasoning behind the bet. Just because the media might spin it as “mathematician doesn’t like the guy proving P!=NP” doesn’t mean the bet is bad. I think it was a great counter-weight to the paper’s hype.
I’m just entering grad school at georgia tech for electrical engineering and look forward to reading more of your blog.
Comment #78 August 12th, 2010 at 12:01 pm
If anyone is to be accused of using the whole thing to get public attention, it would be Dick Lipton, not Scott. In fact, I find his mentioning “social act of accepting it as a proof” (after many holes in the purported proof were already found) totally misleading for the general audience. Unfortunately, Hindu picked up that quote.
And yes, the BBC article is the first one I saw in mass media correctly capturing the essence of P vs NP (i.e., solution vs verification as in jigsaw and its relation to creativity). Scott, thanks for your patience and keeping this blog alive and interesting despite the ungrounded criticism!
Comment #79 August 12th, 2010 at 12:12 pm
Stas, with all due respect,
it’s of course stupid to claim Scott Aaronson
just tries to get public attention.
Claming Mr Lipton is tries to get public attention
out of this is equaly stupid.
Comment #80 August 12th, 2010 at 12:20 pm
McCrank, have you seen the “if” clause in my sentence? I’m not accusing anyone, I’m just saying that quoting the “social act of acceptance” was the worst thing that happened since the proof announcement.
Comment #81 August 12th, 2010 at 12:25 pm
The BBC piece is as ridiculous as any other news item on the subject. The title is especially awful.
Comment #82 August 12th, 2010 at 12:48 pm
Scott, thanks for taking the time to talk to the BBC journalist. Even though it was built wholly upon analogy, that piece was at least coherent.
Comment #83 August 12th, 2010 at 12:55 pm
Seeing the rant posted by Bazooka,
It is getting obvious that there is a reason why the “general audience” expressed massive anger towards Scott’s bet.
Apparently the general audience were mostly concerned about elitism, so when a lay mathematican (well, not quite, say an outsider from complexity) pops out to claim a big problem, it wouldn’t be so surprising that people are sympathetic about him.
Although it is ironic to notice that the actual argument most people referred to were more or less of a variant of “even the best mathematicians expressed interest in his work” — they were simply resorting to another sort of elitism.
On top of that, the ideology behind these thoughts were funny, i.e. the Fields medallist must be correct (and he happened to miss Gowers…) as opposed to all the experts in finite model theory and complexity — all of whom are nasty/mean/…./[insert your favourite word]/etc…
Comment #84 August 12th, 2010 at 12:55 pm
@Stas
In that case i must have missunderstood the
tone of your comment and apologize.
The idea of a top computer scientist who
appears to be the nicest and modest person
in the world being acussed of seeking public
attention got me a bit mad, maybe due to my
nickname 🙂
Comment #85 August 12th, 2010 at 1:02 pm
Scott, thx.
Gil Kalai, it’s nice to read your opinion. Maybe you right that betting market won’t give us a clearer scientific picture on the world. However, would you also disagree that betting markets can give us a clearer picture of what scientists consider likely?
Comment #86 August 12th, 2010 at 1:06 pm
I’d guess (regular guess, not $200k guess) that Bill Mill is right about the sampling bias here, so I’d just like to say that I also thought your bet was productive and entertaining.
It’s a shame that so many commenters decided to indulge their assumptions about your motives instead of giving you the benefit of the doubt, but that’s the internet for you. You made your intentions clear enough to those of us who aren’t convinced of our own psychoanalytic godhood, so I hope you won’t evaluate your actions relative to the lowest common denominator of decency. Keep Shtetl-Optimized weird!
Comment #87 August 12th, 2010 at 1:14 pm
Scott Aaronsohn, like Nassim Nicholas Taleb, you predicted the crash before it happened! You knew some fundamental weaknesses intuitively that the other Myron-Scholes Nobel prize winning economists (computer scientists) fell for!
Comment #88 August 12th, 2010 at 1:18 pm
@Gil
Suppose we set a betting market for the question if factoring is in P. Prominent mathematicians will put their money (and houses) where their mouth is. Will it give us clearer view about the answer? Most probably not.
I’m not sure if I follow exactly. Are you saying that a prediction market would provide no information about which way an open question would be resolved, or just that the market wouldn’t help to resolve the question?
Comment #89 August 12th, 2010 at 1:23 pm
Furd #69: Again with the willful misreading of what I wrote!
As I said before, I CAN afford it, just not very easily. And I didn’t change the terms of the bet: I clarified them in response to questions, arguably making them MORE generous than one would have inferred from the vague original wording.
Comment #90 August 12th, 2010 at 1:31 pm
Crash, Dan Haffey, Bill Mill, Cranky McCrank, Stas, Jacob, Bazooka, everyone else who said something nice: thank you for making my day. You’re the reason why I continue blogging. (Awwwww….)
Comment #91 August 12th, 2010 at 1:32 pm
Personally, I thought the bet was in poor taste. On the other hand, it was also funny and informative, which gets Scott off the hook as usual. 🙂
Comment #92 August 12th, 2010 at 1:56 pm
For another famous example of scientific betting, check out the Simon-Ehrlich wager
For my money (not that I’m risking any), Simon won in the particular bet on commodity prices, but I’m guessing that Ehrlich will probably prove to be right in the longer run (predicting a crisis due to population growth and depletion of natural resources).
Comment #93 August 12th, 2010 at 2:19 pm
Someone wanted to know how Scott could tell so quickly while various luminaries “fell for it”. That’s an interesting question but with a false assumption. Dissecting the proof was something that needed doing no matter how sure one was of the eventual result. Like Scott says, we should be very grateful to those folks for the hard, necessary work.
Let me say again that I think Scott’s bet was highly valuable and even generous. It was a compact, compelling way to convey an important piece of information (very low probability of the proof’s validity). I liked Michael Vassar’s distinction (comment 26) between cheap talk and expensive talk. As for it being generous, you’ll have to agree that it had a fairly high expected value for Deolalikar!
As for the general question of betting markets for scientific questions, see Dave Pennock’s post on the subject: http://blog.oddhead.com/2010/08/11/betting-on-p-equals-np/
Finally, while I’m at it, here’s my attempt to explain P vs NP to my mom: http://messymatters.com/pnp
Comment #94 August 12th, 2010 at 2:22 pm
Amen, Terrence.
Comment #95 August 12th, 2010 at 2:22 pm
@63 and 64
I did go to law school. The ‘bet’ is absolutely enforceable by D – look up ‘unilateral contract’. Furthermore, it’s questionable whether a court would care about the 2019 limitation to yesterday’s offer you made in today’s post; were D to prove P!=NP and then go after you for the $200k. But don’t listen to random anonymous attorney on the web – you must know at least one law professor in Cambridge.
My view (as an attorney, I’m just a bathtub mathematician) is that the bet was ill-advised.
Sky Masterson said it best: One of these days in your travels, a guy is going to show you a brand-new deck of cards on which the seal is not yet broken. Then this guy is going to offer to bet you that he can make the jack of spades jump out of this brand-new deck of cards and squirt cider in your ear. But, son, do not accept this bet, because as sure as you stand there, you’re going to wind up with an ear full of cider.
Comment #96 August 12th, 2010 at 2:24 pm
Here is something that makes me wonder: It would already be exciting enough to prove that P ≠ PSPACE. So why do people jump straight to P ≠ NP? Is it audacious to imply that P ≠ PSPACE isn’t much easier, or is it considered a reasonable possibility?
Comment #97 August 12th, 2010 at 2:26 pm
It is time the blogs take a break and give time to Mr Deolalikar to construct and provide a response to the suggestions, bugs, objections, etc. As I understand, he is still working full time for HP, and needs all the time to work on the proof. Blogs have brought together TCS community and crafted a coherent response to the proof and done the job. The bet, and additional discussion will be a lot pf pressure on him to respond quickly. The blogs need to set an expectation of the time line of his response and take a break to re-convene later.
Comment #98 August 12th, 2010 at 2:37 pm
IMHO, Scott perfectly explained what a P vs NP proof would be after in his talk during the last year Barriers workshop (slides and video available here, I was fortunate to listen to it live.) The purported proof doesn’t look like being up to those expectations (e.g., making most of the known lower bound results a special case of it), so it was reasonable that Scott made the bet without checking the details.
Comment #99 August 12th, 2010 at 2:42 pm
Scott:
I think anyone with a clue understands what the bet was about, and probably had a chuckle. It is a waste of time defending it.
Comment #100 August 12th, 2010 at 2:47 pm
@Greg: Millenium prize and the corresponding prize money, publicity and awards that would surround such a proof? P \neq PSPACE, NL \neq NP would be smaller events comparatively.
Comment #101 August 12th, 2010 at 3:00 pm
I actually liked this tempest in a teacup, because it reveals a lot of things about how scientists (or, in this case, mathematicians) grok communications in their own circle vs. the outside world.
Scott, my $0.02 -> the bet wasn’t nasty. It was a perfect way to communicate a science/math news story to non-scientists/mathematicians. My gut response when someone posted the original slashdotted blog post and asked me what I thought was, “Well, I won’t bet my arm that it’s flawed/wrong somehow, but if you forced me at gunpoint to bet my arm on *something*, this would be it.”
It’s not unreasonable to bet against *anybody* claiming to have a winner to any specific Clay Problem. They’re Clay Problems for a reason; they’re freaking hard. Most likely, the person who eventually publishes a winner to a Clay Problem won’t be publishing the winner as a complete entity on the first go.
In fact, it’s pretty likely that you’re going to have someone building off of a previous published attempt (perhaps their own).
So, for some non-mathematician asking, “Hey, is this for reals?”, “I bet my house that it’s likely not” isn’t an unreasonable way to communicate to the layperson exactly *how* improbable it is that someone got it right on the first published try.
Personally, if I had the gumption and the brains to tackle a Clay and I actually thought I might have it, I’d be *expecting* a majority of the community to expect me to be wrong, even if I was a Giant in the Field (which, clearly, I’m not). That’s not because it’s a reflection on *me*, it’s because it’s a reflection *on the problem*.
Anyway, Raoul #100, +1
Comment #102 August 12th, 2010 at 3:25 pm
Gil Kalai:
I couldn’t disagree more.
Your argument isn’t specific to scientific betting markets at all; it can be equally well used to show that any given prediction market can’t work. Take the stock market, for example. The function of the stock market is, for its participants to make money and for its observers, to provide useful information as to expected profitability of corporations. With the stock market, it is also true that if all private information of its participants were made public, it would be sufficient for observers to determine the true state of the world. But it does not follow from this that the stock market is not relevant or useful as an information-aggregating device.
In your post, you are vague as to what you mean by “the true state of the world.” In the context of Delalikar’s proof, is the true state of the world whether or not the proof is correct, or the actual reasons why the proof is correct or not? If the latter, then it’s true, a betting market can’t help much. But if the former, then a betting market is actually more informative than “making all private information of participants public,” for three reasons. First, a betting market allows for expressing beliefs that can’t be supported by a rational argument (“I just have a strong hunch”). Second, betting markets convey information more efficiently than public revelation of private knowledge. The amount of all private knowledge relevant to a question as complex as “P versus NP” is so huge that no individual can possibly process all of it. Market prices compress all that information into signals that are much easier to process. An third, a scientific prediction market would offer information about open scientific questions in the form that would be accessible to everyone, not only scientists. To me as a theoretical computer science ignoramus, Aronson’s bet is actually much more informative that a detailed refutation of Delalikar’s proof, because I have no qualifications to judge the technical details. I have no idea why a proof that shows 3SAT is not in P should fail for problems like 2SAT and XOR-SAT. In fact, I barely know what 3SAT, 2SAT and XOR-SAT even mean. But I do know the exact meaning of $200,000.
Comment #103 August 12th, 2010 at 3:34 pm
Here’s my 2 cents:
I’ve previously worked for HP Bangalore as a software engineer. HP kind of had 3 divisions in Bangalore: Labs, Software and Consulting/ Outsourcing.
The division I worked for, Software had quite an emphasis on innovation. We had the option of research disclosures, or patents. Some of the walls in our building were covered with framed certificates of innovations made by local employees. I found the environment to be tremendously empowering for innovation, especially my boss was really encouraging!
To extend this, I can only imagine what the environment would be like at HP LABS in the US, where Vinay hails from! So it would be for HP Labs Bangalore!
I have graduated with an M.A. in CS at Wayne State before.
But I’ve never felt as empowered to publish anything, even though I think learnt an irreplaceable lot there!
So in fact, I published my first paper, a research disclosure while at HP. And, I was brimming with so much confidence that I published a book AFTER I left HP.
http://amzn.com/1452828687
Even though Vinay’s (and possibly mine) attempts may turn out to be duds, I would encourage you to keep an open mind. Don’t hang us for trying!
The state of affairs is reflected in the fact that, even though there are a ton of brilliant people in US schools, somehow they do not seem to have the confidence or initiative to do great stuff. Maybe its the government funded central research that’s killing innovation. Everything is mired in “String theory” to please the NSF and NIH stuffed suits.
While I was studying in the US, I just thought of my school’s low ranking and that I could possibly never do anything considering my low perch! But I now realize that even people sitting high up in US universities are too strait-jacketed to do anything. No wonder, an outsider, Grigoriy Perelman could develop on Richard Hamilton’s Ricci flow to confidently give his solution. On arXiv.
In the end, I’m a strong believer in the future of corporate innovation.
Go HP!
Milz
Comment #104 August 12th, 2010 at 3:36 pm
Millenium prize and the corresponding prize money, publicity and awards that would surround such a proof?
In other words, let’s not waste our time juggling eight pins, if there’s a PRIZE for ten pins.
One would hope that Deolalikar or anyone else has a better reason than that for passing over P ≠ PSPACE in favor of P ≠ NP.
Comment #105 August 12th, 2010 at 3:41 pm
Relevant to Tim Converse’ account of the Simon-Ehrlich wager (Comment #92) is von Neumann’s 1955 article Can We Survive Technology?, which is collected in a symposium proceedings sponsored by the Forbes Corporation, titled The Fabulous Future: America in 1980 (it can be found on Google Books).
Von Neumann foresaw that by 1980 we’d be living on an overheating planet that was running out of oil. Obviously he got the physics and economics mainly right … only the timing was a little bit off.
Perhaps Vinay Deolalikar too has got it mainly right, but not completely right, about proof technologies for P≠NP … just as Richard Hamilton got it mainly right, but not completely right, about proof technologies for the Poincaré Conjecture.
That is the point-of-view that Terry Tao’s most recent post on Dick Lipton’s blog is suggesting: “Do we believe Claims 1 and 2 to actually be true (regardless of whether Deolalikar’s proof is valid)? If we believe them both to be true, then this is still a non-trivial and potentially viable strategy towards P≠NP.”
This, it may be that Vinay Deolalikar will prove to be the Richard Hamilton of P≠NP … and if so, who are likely candidates to fill the role of Grigori Perelman?
Inspired by Scott’s example, I hereby bet $200,000 that it won’t be me. 🙂
Comment #106 August 12th, 2010 at 4:34 pm
Greg Kuperberg: Indeed, there are many, many intermediate questions one should try to answer before P vs. NP — P vs. PSPACE is one example, though my own intuition puts it only one or two rungs below P vs. NP itself. Other examples include L vs NP, NEXP vs P/poly, permanent vs determinant, P vs NP in the Blum-Shub-Smale model… I think in terms of dozens of nontrivial “rungs” between what we know now and P!=NP. If a paper claims to jump k of those rungs in one go, without even recognizing that they *are* separate rungs, its prior probability decreases exponentially (double-exponentially?) with k. That already gives one answer to the question people were asking above, of how one could figure out immediately on reading it that Deolalikar’s proof wouldn’t stand.
Comment #107 August 12th, 2010 at 4:42 pm
@Greg: I was not defending going straight for P \neq NP. I was just trying to give reasons for why there are so many “proofs” for P vs. NP compared to other more intermediate problems.
Comment #108 August 12th, 2010 at 4:55 pm
JD #95: Ah, you see, but there’s a fundamental difference between betting that a jack of spades can’t jump out of a brand-new deck of cards and squirt cider in your ear, and betting that you can’t prove P!=NP without actually doing the hard work of separating 3SAT from all the problems in P (2SAT, XORSAT, matching, linear programming, holographic problems…) In the former case, you’re betting on the reliability of your frail, savannah-optimized senses, as well as on the incompetence of the magician. In the latter case, you’re betting on the comprehensibility of the world itself.
Comment #109 August 12th, 2010 at 5:05 pm
I agree with Greg that P =! PSPACE is extremely exciting and I am sure if people had ideas how to attack it they would. I wonder what can be said about a world where P=PSPACE. Are there spectacular more things that happen in such a world compared to a world with P=NP?
Regarding betting markets for scientific questions: Jiav, I do not think it is a good way to learn even what scientists think, a better way is to simply ask.
Przemek: “With the stock market, it is also true that if all private information of its participants were made public, it would be sufficient for observers to determine the true state of the world.”
You missed my point. For scientific questions the information is simply NOT there. It is NOT true that even if all private information will become known we will know the answer.
I talked about James Miller idea and not specifically about betting on the corectness of a specific paper.
(For such a bet I simply dont understand what is the point. The paper is available, people are reading it, it is clear that in a few days or weeks we will have a much better picture, what is there to be gained from betting? )
Nevertheless, regarding your detailed explanation of why
“a betting market is actually more informative than “making all private information of participants public,for three reasons.” I must admit none of your three reasons make sense to me. ALL three look to me as going in the wrong direction.
Comment #110 August 12th, 2010 at 5:07 pm
Terrence, you need to appreciate that Scott’s blogging/lecturing style is solidly grounded in cognitive science: a substantial body of experimental evidence has established that pretty much anyone’s IQ increases by about 10 points whenever they suspect they are being swindled, tricked, made-fun-of, or conspired-against. That is why so many effective lecturers (like Scott) emphasize jokes and paradoxes: they literally make their audiences smarter by doing so.
Thus, the various controversies surrounding Vinay Deolalikar’s proof are making everyone smarter … which is great fun, provided one doesn’t take any of these controversies too seriously! 🙂
A keen practical appreciation of this point is found in Craig Venter’s autobiography A Life Decoded, in which a senior government official remarks: “Son, you are obviously doing extremely well. This is Washington, and we judge people by the quality of their enemies, and son, you’ve got some of the best.”
For this reason, the collective intelligence of the CS community is undoubtedly higher this week than it has ever been before … and so we had all better “make hay while the sun shines.” 🙂
Comment #111 August 12th, 2010 at 6:28 pm
I am still yet to see any non-nerdy objections to Scott’s $200k offer.
Comment #112 August 12th, 2010 at 6:50 pm
P != NP, I have a truly simple proof but it is too large to fit in the character limit of this blog comment.
Comment #113 August 12th, 2010 at 7:22 pm
@110
Scott,
Hate to harp on this further – but don’t want people reading your blog to think it is a good idea to make these kinds of offers. Because while you almost certaily ‘safe’, somebody will take the jack/cider bet and end up with cider in their ear (and a 200,000 lien on their house).
Prepoints (1) I don’t know D but suspect that D would never try to enforce the contract even in the unlikely event he prooved PNP (if for no other reason than promoting academic harmony); (2) I understand that is highly unlikely that even given a greatly enhanced lifespan due to improvements in medical technology in the coming years that D would ever prove, or come close to proving PNP. (3) and the main reason I’m writing this, I am not like D, if someone made an offer like this to me and I was capable of accepting by performing I would absolutely do it, and if I succesfully performed I would sue to enforce the contract in court and I would win – there are far more people like me than like D – so kids, please, don’t make these offers at home.
Your point #2, that your $200,000 is safe is wrong (if by safe you mean 0% chance).
1a. You wrote ‘his proof’ not ‘this proof’ in your offer. So a hypothetical future proof of his that is awarded the prize loses you your money.
1b. You didn’t qualify the offer with something like ‘solely authored’ so a hypothetical future proof of his, that is co-authored, and that is awarded the prize loses you your money.
2a. His continued work on the proof after you posted your offer could constitute acceptance by performance if D brought a case to enforce the contract (which he won’t, but again that’s not the point here).
2b Whether the later added timelimit qualification will fly is an open question particularly if D continues to work on the problem (continues to perform).
Note (1) You have a good argument if D abandons the problem and does nothing for 6 or 7 years before restarting work on it before proving it.
Note (2) that there are reasonableness limitations in the law but since you tied your offer to an open-ended prize where the expectation is that it would take many years before some of the problems are proved (if ever) – one could make a case that as long as the prize is up, and as long as D continues to perform on the problem, your bet is up.
* * *
A sticky wicket with unilateral contracts is that generally, once acceptance by performance has started (in this case D continuing to work on the proof) the offeror (that’s you) can’t rescind the offer.
Comment #114 August 12th, 2010 at 8:06 pm
Gil, is it wrong of me to conclude from your arguments against prediction markets for mathematical theorems that you believe mathematicians intuition about open problems has no ability to predict the final resolution of those open problems?
Aside from potential ethical issues with gambling, would you take an even money bet that P = NP?
Comment #115 August 12th, 2010 at 8:30 pm
Just my $0.02 on this bet thing. Where is the bet? It’s like me saying to my kids, I’ll buy you an ice-cream if you get your homework problem correct. Who is he betting with?
If he just wanted to assert that he had a credible objection, there are many ways. Reputation is one. Unless a person is known for making off the wall comments, people will give credence to the opinion of an eminent mathematician who feels a proof is wrong.
In fact, while Scott certainly conveyed a strong and credible opinion with the offer, he did the wrong thing regarding future credibility. On his future comments, people can ask, well what money do you place on your opinion. It’s just unnecessary.
But thanks for making the blog a fun read.
Comment #116 August 12th, 2010 at 8:45 pm
I am wondering the same thing as Rob Renaud.
I think the confusion might be about who knows what. It might be that a mathematician who knows all the ins and outs of a problem or of a proposed proof gains no information from a prediction market around it. Similarly, perhaps one could say that the mathematics community doesn’t learn anything that it didn’t already know from such a market, because the prediction market makes no new information public that wasn’t public already. This seems to me to be the view that Gil is taking. (Is that right?)
However, if one considers the point of view of the layman, he or she might be able to form a much clearer idea of the likelihood of some outcome or another when presented with the predictions of the market rather than the reasonings of the experts. I believe this is the point that przemek was making.
So whether prediction markets about the progress of mathematics would add any knowledge depends on who is doing the knowing.
Comment #117 August 12th, 2010 at 8:46 pm
I thought the bet was an interesting idea — but then I discovered it on an economist’s blog. Your offer gave us some sense of your confidence in your prediction. By comparison, it’s particularly telling that Vinay Deolalikar has not offered to sweeten the prize pot by $200,000 — which would not seem much of a risk if he’s sure he’s right. Then again, he’s already taken a substantial risk by spending so much of his life trying to solve this problem. Maybe that represents enough of a commitment.
All in all, it was a fun thing to do, but we should all probably hope it does not become a trend.
Comment #118 August 12th, 2010 at 9:44 pm
My only objection to the $200,000 bet is the credibility. While it isn’t ridiculous like $1,000,000, I still get the hunch that most people making the bet would probably back out if they lost. I’m sure your blog isn’t legally binding afterall, and while your reputation would suffer it probably wouldn’t suffer $200,000 worth.
That’s not to say that you aren’t being honest, nor that you wouldn’t actually follow through, but it’s still enough that it’s not completely credible to me.
My advice would be a bet in the range of $10,000-$50,000, it’s still large enough to show that you really doubt it will work, but it’s also small enough that I don’t doubt you’d pay it off in the unlikely event that you lost. On the whole I’d probably take someone making a $20,000 bet more seriously than a $200,000 bet.
Of course you could also set up some contract where you were legally obliged to pay the $200,000, but that’s probably more trouble than it’s worth.
Comment #119 August 13th, 2010 at 12:35 am
I’m not sure what some people are thinking. This $200k bet is absolutely 100% real. And if Deolalikar wins, there is no reason for him not to accept the money.
If you haven’t understood that $200k is really on the line (albeit withseemingly vanishingly small probability) then you have had no clue throughout this whole thing.
Comment #120 August 13th, 2010 at 1:09 am
Rob, no there are many cases where we know the answer but dont have a proof. I simply see no advantages (and many disadvantages) for a betting market compared to simply asking.
Comment #121 August 13th, 2010 at 1:16 am
The idea of prediction markets about scientific questions as a meam to let laymen learn about science in a non technical way is also quite absurd.
You can regard the existing casinos as a betting market aimed to teach laymen the basics of probability. Learning is extremely slow though.
Comment #122 August 13th, 2010 at 1:41 am
You can regard the existing casinos as a betting market aimed to teach laymen the basics of probability.
I can’t see that as the intention, because they have distractions to get people to stop thinking.
Comment #123 August 13th, 2010 at 1:52 am
@Gil
In hiring a resarcher at your institution and paying them a salary and funding for their research proposal, you are implicitly betting that he/she will give you good results in the future. You are quite sure that they will be good a good bet or fit for your institution.
Again when you are spending your money and time on a particular approach to P and NP, you are betting that will work and finally pay off.
But it may turn out to be entirely different, as in this case.
Comment #124 August 13th, 2010 at 2:16 am
Przemek,
Do you know about the Milgrom-Stokey “no trade theorem”? How do your views fit with it?
Best,
Ben
Comment #125 August 13th, 2010 at 3:07 am
@Gil Touché re: casinos.
Comment #126 August 13th, 2010 at 3:29 am
Hello there, here’s a comment I just posted on nature’s website on betting and P vs. NP 🙂
Working on one of the Millenium Prize problems, like P vs. NP implicitly constitutes betting.
The one-time financial payoff is $1,000,000. There is also a lasting glory payoff for people or cultures who prefer that over money.
Assume there are 100,000 people thinking about this problem at any time. Even if each one of them spends $10 of their time/ money/ effort on this, $1,000,000 has been already invested in the effort! Then think of all the websites and communications infrastructure involved, and maybe a few jobs were created in the process!
Cumulatively over a period of the last 10 years, since the award was instituted by CMI, this figure would be more like $10,000,000 collectively invested on P vs. NP alone!
Only a couple of people would be getting the final payout. So the chances are now maybe 1/100,000, or 0.00001 of any thinker winning this prize.
So is this starting to look more like the lowly lottery ticket now?
The effort also counts. As you may be aware, Grigoriy Perelman credited Richard Hamilton’s Ricci flow for his solution of the Poincare conjecture. There would be other smaller researchers with less significant contributions involved too.
These problems could have (and have) existed even without the millenium prize. But instituting the prize serves as a disproportionate incentive as compared to the collective investment. The actual wealth generation involved is actually more than the value of the prize itself!
Humanity may have so far spent $10,000,000 or more on P vs NP, counting research funding to top researchers, individual time that could have been spent in other lucrative pursuits etc.
But that money has to come from somewhere!
So people have spent their time making money in other directions to invest in this effort, without realizing it, spending on P/NP instead of on food! Hence the disproportionate wealth generation.
So time, money and the contributing research efforts that also come at a price paid to researchers in terms of research funding!
Even if you just consider there are only 10 researchers at the top who are real contenders, each one has just a 10% chance of winning, pitted against the remaining 9!
So you see, the lottery and gambling is great for the economy, it can generate wealth 🙂
But because of social restrictions, we just don’t officially think of P vs. NP as “gambling”, because gambling is what only the unsophisticated “lowlife” is supposed to indulge in!
Remember, after all, even to buy a lowly lottery ticket, the buyers have to make that money somehow by working and producing!
Money is Made, not Earned! It’s just a real powerful concept, like Niall Ferguson explains in
“The Ascent of Money”!
Milz
Comment #127 August 13th, 2010 at 3:44 am
Hi there, here’s a comment I posted about P vs. NP and betting on nature’s website 🙂
Working on one of the Millenium Prize problems, like P vs. NP implicitly constitutes betting.
The one-time financial payoff is $1,000,000. There is also a lasting glory payoff for people or cultures who prefer that over money.
Assume there are 100,000 people thinking about this problem at any time. Even if each one of them spends $10 of their time/ money/ effort on this, $1,000,000 has been already invested in the effort! Then think of all the websites and communications infrastructure involved, and maybe a few jobs were created in the process!
Cumulatively over a period of the last 10 years, since the award was instituted by CMI, this figure would be more like $10,000,000 collectively invested on P vs. NP alone!
Only a couple of people would be getting the final payout. So the chances are now maybe 1/100,000, or 0.00001 of any thinker winning this prize.
So is this starting to look more like the lowly lottery ticket now?
The effort also counts. As you may be aware, Grigoriy Perelman credited Richard Hamilton’s Ricci flow for his solution of the Poincare conjecture. There would be other smaller researchers with less significant contributions involved too.
These problems could have (and have) existed even without the millenium prize. But instituting the prize serves as a disproportionate incentive as compared to the collective investment. The actual wealth generation involved is actually more than the value of the prize itself!
Humanity may have so far spent $10,000,000 or more on P vs NP, counting research funding to top researchers, individual time that could have been spent in other lucrative pursuits etc.
But that money has to come from somewhere!
So people have spent their time making money in other directions to invest in this effort, without realizing it, spending on P/NP instead of on food! Hence the disproportionate wealth generation.
So time, money and the contributing research efforts that also come at a price paid to researchers in terms of research funding!
Even if you just consider there are only 10 researchers at the top who are real contenders, each one has just a 10% chance of winning, pitted against the remaining 9!
So you see, the lottery and gambling is great for the economy, it can generate wealth 🙂
But because of social restrictions, we just don’t officially think of P vs. NP as “gambling”, because gambling is what only the unsophisticated “lowlife” is supposed to indulge in!
Remember, after all, even to buy a lowly lottery ticket, the buyers have to make that money somehow by working and producing!
Money is Made, not Earned! It’s just a real powerful concept, like Niall Ferguson explains in
“The Ascent of Money”!
Milind Bandekar “Milz”
Comment #128 August 13th, 2010 at 5:30 am
So here is my completely non-expert bet. When we do finally prove it, the result is going to be less important than the method. It will be the isometric problem all over again. We just need our own calculus of variations to show up.
Give it a thousand years. Proving P?NP (okay I really wanted to put /=) will be a homework problem for high school kids.
I feel like software engineers of today are to the CS theorists of the future, what the Egyptians surveyors were to the Greek mathematicians. They gathered the empirical evidence needed to make the universal generalizations. Patience, patience, patience.
Comment #129 August 13th, 2010 at 6:29 am
Scott:
I am glad that you have seen the photons at last! Your updates show this.
Do note that commenters have not assigned the least charitable interpretations to your writing. In fact, that is the rub: we did not expect you to say something that had such an obvious “least charitable” interpretation, and it is that that many pointed out. As in “Gosh, Scott, how could you commit such a faux pas?”
That people pestered you to say something is really no defense for pulling such an antic! I am in so much agreement with YISONG above, that we might pass for entangled bosons. Had you mentioned that you had given the manuscript its due before filing it away in the betmylastshirt file, your comment would have been seen in the manner you wanted it seen. Note that here, it is not the case that most of us didn’t know that you might have read the manuscript. Indeed, anybody who knows you would guess that you might have. Yet, this is not sufficient to let you off the hook; you still wrote something that would offend those who don’t know you.
Anyway, it’s too late to do much about it. The laughing gas is out of the balloon and all one can do is open the windows. Now look for a photo op with VD, and smile.
Comment #130 August 13th, 2010 at 6:39 am
Hi,
after reading the slides made by Scott on the P vs NP question i understand better why he was so sure on betting against the attempt made by Deolalikar to solving the monster question 😛
I would like to ask: is there a real possibility that P vs NP is unprovable?
How could that be possibile? Is there people trying to understand better this possibility?
If P vs NP turns out to be unprovable, people will continue to spend their time trying to do an impossible thing…
Maybe we will arrive at a proof only when the cumulative effort of researchers will be such that the last step needed in order to prove the devil problem will be relatively easy…(i mean, we will see a really long list of small steps instead of a giant one)…
O_o
Comment #131 August 13th, 2010 at 6:45 am
“Maybe we will arrive at a proof only when the cumulative effort of researchers will be such that the last step needed in order to prove the devil problem will be relatively easy…(i mean, we will see a really long list of small steps instead of a giant one)…”
Ok, that is obvious, but what i really wanted to say is that we are probably (given the current knowledge) really far away from the possibility of proving P vs NP…
Or not??
Comment #132 August 13th, 2010 at 7:22 am
I should just grin and bear it, even if journalists brush aside the experts’ boring, hard-to-explain technical reservations, and write article after cringe-inducing article exclaiming that “P≠NP HAS (APPARENTLY) BEEN PROVED!!!”
Could you provide a link to the media-coverage you found particularly cringe-inducing? (Disclaimer: I may have written some of it.) It doesn’t seem unreasonable to me to report on the fact that a proof has been offered, by a reputable researcher, and is being taken seriously by the CS community. Hell, it doesn’t even seem unreasonable to get a bit excited about it. Obviously it would be unforgiveable to fail to mention that that the paper had to pass a great many tests before being accepted as definitive, but I can’t find any reporting which is guilty of that.
Obviously we could always play the game of deliberately seeking out crank claimants of Millennium prizes and then hyping up them up to the max. But I don’t think you can argue that’s what happened here. The fact is that when the paper first emerged, there was a great deal of excitement about which began with the experts (notably Steve Cook and Dick Lipton) and then spread from there. You were skeptical from the outset, and it looks like you were right to be, but before the dream team really swung into action there was a fair amount of cautious optimism about – that wasn’t a media invention.
Comment #133 August 13th, 2010 at 7:26 am
Broken link – it should go to here.
Comment #134 August 13th, 2010 at 7:27 am
#58:
Probably no-one knows that. Perhaps in the distant past an author made a mistake… Or Two-authored paper became a paper with just one author and those “we” remained… And that would be the funny story when lots of people trying to learn how to professionaly write a scientific paper, by reading this one paper, propagated this nomenclature.
Comment #135 August 13th, 2010 at 7:33 am
Or here, Richard.
http://www.saudigazette.com.sa/index.cfm?method=home.regcon&contentID=2008062910436
Comment #136 August 13th, 2010 at 7:35 am
I do not think the bet was offensive. In fact, from a PR perspective, I think it was extremely helpful. And I don’t just mean helpful for Scott.
Many news outlets either do not and understand science or do not care about the scientific process. “Million $ math problem solved” is a good headline. They are reluctant to water down the great story just because it is everything but certain (nobody really had time to have a careful look at the proof) that the proof is correct.
Scott gave them something equally exciting to report that stands in opposition to the hype. It simply helped to prevent that the public prematurely excepts something as a certainty, before it was subjected to the peer review process. And for this, I thank Scott.
Comment #137 August 13th, 2010 at 7:36 am
My own opinion is that three people who are coming-off exceedingly well in this episode are Vinay Deolalikar, Dick Lipton, and Terry Tao.
Since not too many people will take issue with that assertion, let’s add some “spice” by asserting that this virtuosity arises because Vinay Deolalikar, Dick Lipton, and Terry Tao all are behaving irrationally: (1) Vinay Deolalikar has irrationally worked hard at a high-risk challenge in a field in which he is a non-expert, (2) Dick Lipton has hosted a blog that focuses on the thankless task of community-building, and (3) Terry Tao has reasoned non-deductively, specifically in focusing upon “loopholes” in addition to deductions, per Tao’s most recent post that “perhaps there is still some loophole that may offer a way to salvage the strategy at least of Deolalikar’s argument, if not an actual result.”
It’s fun (IMHO) to consider the aggregated Deolalikar/Lipton/Tao irrationality in the light of a recent Phil. Trans. Royal Soc. Series B (aka “PTRS-B”) theme issue titled Rationality and Emotions (January 27, 2010). So let’s see how much “rationality and emotion” we can compress into four short paragraphs.
First, the PTRS-B articles document that both high IQ’s and rigorous training serve well to create ingenious justifications for behaviors that are self-serving; thus intelligence and education provide less protection against irrationality than might be expected. Reinhard Selten’s memorable aphorism “Game theory is for proving theorems, not for playing games” reminds us that irrational motivations can be encoded even into mathematical postulates and axioms.
The encoding of essentially irrational motivations in axioms occurs in the sciences too: “So, what is quantum mechanics? It’s not a physical theory in the same sense as electromagnetism or general relativity: quantum mechanics is the operating system that other physical theories run on as application software” (Google it! 🙂 ).
Some well-known examples of math/science operating systems that proved too constraining are: (1) “the earth is flat”, (2) “Newtonian space is flat”, (3) “Hilbert space is flat”, (4) “species are unchanging”, (5) “one gene, one protein”, (6) “biology is an experimental discipline” and of course (7) “human economic behavior is rational.” Despite what Gauss called “the outcries of the Boeotians”, mathematicians and scientists are constantly upgrading their operating systems … often against axiom-embracing factions that view themselves as rational (but really aren’t).
If we are very fortunate, then perhaps Terry Tao’s hopes will be realized as follows. Just as Grigori Perelman’s geometric surgery repaired Richard Hamilton’s proof strategy, perhaps a similarly ingenious surgery can be found to repair Vinay Deolalikar’s proof strategy. If we are willing to disregard the outcries of Boeotians, then we can extend this surgery even to fundamental definitions and axioms. For example, we are free to seek restrictions of P that encompass our ordinary algorithmic intuitions, and for which Deolalikar’s proof strategy can be implemented rigorously. This I take to be Terry Tao’s essential point.
That’s *one* way to extract a happy story from this deeply thrilling episode, anyway! 🙂
Comment #138 August 13th, 2010 at 7:40 am
I appreciate the correction regarding the legal status. I guess my interpretation was that Scott’s award was dependent on whether an already published proof turned out to be correct and thus there was no consideration. (The work already having been done.)
As a separate issue I would point out that Scott’s offer is not really a bet since he wins nothing by being right. You would not describe the Clay prize as a bet that no one will solve the Millennium problems, right?
Comment #139 August 13th, 2010 at 8:11 am
#139 VD will have no insurance left for surgery after hp fires his ass into outer space… with a 103 page 12 pt pink slip. Any bets as to what VD’s future looks like? Does it involve a name change, plastic surgery, food stamps, recycling soda cans …
Comment #140 August 13th, 2010 at 8:35 am
@Why?: “We” are the author and the reader(s).
Comment #141 August 13th, 2010 at 9:50 am
@Ted 141:
It has taken lots of energy and time from us, but I think you probably don’t understand how things work here. Think about what would happen if venture capitalists did the same thing. Failure of his proof will not be fatal, he has received lots of kind remarks (maybe too kind) from experts in various areas, and I am sure he and every other mathematician will be much more careful in making similar claims in future. IMHO, up to this point he has acted relatively responsibly and I hope that he would make an announcement retracting his proof when (if) he understands that this approach cannot be fixed. Even in the case that none of his ideas remain interesting he should not be punished for trying, neither by community nor by HP.
This has been a huge cheap good publicity for HP, and it has been a beneficial affair for complexity theory also. I can already see a few interesting questions we should work on which came out of this affair. This MMPR (massive multi-player peer review) (specially what Dick, Ken, Terry, Suresh, … did) has been an exciting experiment, with positive social and methodological effect, but it also has a considerable cost so I think we should be careful in doing a similar one in future.
It would be useful to collect and write down a new list of criteria for considering a P vs. NP proof in future.
Comment #142 August 13th, 2010 at 10:05 am
Anonymous’ post above is so exceedingly sensible, that “anonymous” should consider attaching a name to it!
It is well to reflect though, that an Kenneth Arrow-type principle almost surely would apply to any “new list of criteria for considering a proof.” Namely, no matter what consideration criteria were proposed, skeptics would point to famous proofs whose first presentation violated those same criteria.
It may well be that our present system of scientific peer review, with all its ungainly compromises, is as Winston Churchill memorably said of democracy: “the worst system, except all the others that have been tried from time to time.”
Comment #143 August 13th, 2010 at 10:15 am
IMO, we need an idea sharing and discussion forum for TCS community. Mathoverflow is not suitable and does not permit discussion, and I guess TCSoverflow will be similar. Blogs are not designed for discussions. I suggest the following address forum.computationalcomplexity.org (if Lance and Bill agree with it).
Comment #144 August 13th, 2010 at 10:20 am
#142 (“We”):
This does not hold… How come the author and reader(s) “report”, “propose”, “show”, “prove”, etc? The author, no problem. But the reader(s)? This is not it! Any other shots?
Comment #145 August 13th, 2010 at 10:54 am
@#146 (lo):
This is a common practice in math literature. Read Knuth’s note’s on writing mathematicsn.
Comment #146 August 13th, 2010 at 11:30 am
Students wishing to learn a classical mathematical writing style can enjoyably do so by reading Gauss 1828 Disquisitiones generales circa superficies curvas either in the original latin, or in the english translation General Investigations of Curved Surfaces of 1827 and 1825 (both available in fulltext on Google Books). This is the work in which Gauss’ celebrated Theorema Egregium first appeared.
And yes, Gauss uses the individual “we” idiom throughout … it’s mighty enjoyable to see how this one mathematician’s work embodies pretty much *all* of today’s conventional mathematical usages.
Not only did Knuth carefully study Gauss’ classical mathematical idioms, Knuth also studied the classical mathematical typography of the era. Hint: look up the history of “Garamond.”
Comment #147 August 13th, 2010 at 11:49 am
From the BBC report: “Dr Deolalikar published his proof…” Don’t science journalist realize that the word ‘publish’ is loaded in an academic context?
Comment #148 August 13th, 2010 at 11:54 am
For BBC, publish can mean whatever Queen Elizabeth decrees that morning after tea and biscuits.
Comment #149 August 13th, 2010 at 11:58 am
First, I’d like to thank Scott (and others) for:
A.) Adding a few fun words to my vocabulary (magisterial, meshugenner) over the last few days, and
B.) Entertaining me over the past few days — this discussion has been a lot of fun for me.
C.) Saving me the effort needed to digest the latest 100 page “breakthrough” that was posted on slashdot.
Second, I’d like to ask Scott to comment on the following observations
A.) It seems to me that it appears the P vs. NP question is much, much harder to resolve than, for example, Primes is in P, Fermat’s last Theorem, the Poincare Conjecture, etc. For the others on this list of recent breakthroughs, some steady progress was made leading up the eventual, surprising, solution. Also, the barriers to these other problems were not as high. Here, it seems like we are still a long way away and the barriers are significant. (E.g., we still can’t prove a O(n^3) lower bound on 3-Sat.) Maybe the Clay Prize should be $100 Million for this one. What’s your assessment?
2.) It seems to me that in the Prover/Verifier model of the current state of mathematics/theoretical CS, we are still putting a lot of mental effort on the verifier, and not providing enough automated support for referees. So, someone can give a “100 page proof” of P vs. NP that has to be carefully looked at by a number of people to verify that it is correct. That’s a significant use of resources that may or may not be warranted.
As a member of the TCS community who also does a fair bit of software development, I feel that at some point we (the TCS/ mathematics community) should be putting more of the weight of the prover/verifier onto the prover. (I.e., don’t give me a 100 page program that I have to compile by hand.)
Just like a program, it should be the case that this P vs. NP proof could be “coded” in a particular “language of mathematics” (e.g., HOL), and then the question about whether the proof was correct would be simple and more or less automatic. Vinay would win his prize more or less automatically, and we wouldn’t have to spend a lot of time talking about whether or not was true. (We would be talking about *why* it was correct. )
In this particular case, then the mental effort of verification would be
shifted to the “prover” who would be fighting with “compilation bugs” before showing it to anyone, and not continually sending “new versions” for the community to “compile.” This would greatly decrease the number of new, but incorrect “P vs. NP” “proofs.”
This is the current way software development works.
If we had better tools for “mathematics development”, maybe we
could get there. Any comments about how far we are away from such an approach and whether or not such an approach might even be desirable?
Comment #150 August 13th, 2010 at 12:45 pm
DJOhio asks: Any comments about how far we are away from such an approach and whether or not such an approach might even be desirable?
Sure! It seems (to me) that Terry Tao is giving Vinay Deolalikar (and everyone else) a very useful hint when he writes: “Errors are first originating in the finite model theory sections but are only really manifesting themselves when those sections are applied to random k-SAT and thence to the complexity conclusions.”
Contemplating Tao’s insight, we see that one option for Deolalikar is to restrict P to a weaker computational model, such that his proof (or a modified version of it) does go through.
That suggests a line of inquiry that is very natural for engineers: Can we weaken the mathematical definition of the complexity class P (we’ll call the weaker version P’), such that P’ still captures the practical engineering definition of PTIME computing, and yet Deolalikar’s technology for P’/NP separation works?
As a bonus, this points to a natural explanation of why P≠NP is so unexpectedly hard to prove, namely, it’s not quite the right question to ask.
We engineers have embraced similar strategies quite often, and with considerable success, e.g., if quantum simulation is hard on Hilbert spaces, then move your simulation to a more favorable state-space. In disciplines as diverse as computational fluid dynamics, lattice gauge theory, density functional theory, and even string theory, this strategy has led to considerable mathematical and practical success … so why shouldn’t it work for P≠NP too?
Comment #151 August 13th, 2010 at 12:55 pm
I can’t wait for the promised version after 3-4 days. Scott is definitely eager too.
Turn off all your electronic devices and go to a beach rave instead, Scott. I feel sorry fo’ ya.
Comment #152 August 13th, 2010 at 1:06 pm
DJOhio #151:
Try the following experiment: download HOL or Isabelle and try to encode from scratch some well known and classical theorem like say the Riemann mapping theorem in it. You will quickly understand why mathematicians aren’t rushing to translate all their proofs this way.
That being said I hope that in the future this process will become painless. Hopefully somebody will design a computer system which can process human written proofs and automatically translate it into a form which can be input into a theorem prover.
With regard to the claimed proof it seems too many people are focusing on the money. I find this ridiculous, there are far easier ways to make a million bucks than to prove a Clay problem. I think it would perhaps have been better if the Clay foundation had set the prize at $1000 thus making it clear that it was only symbolic. Then perhaps the unedifying spectacle of people presuming to advice Dr. Perelman about taking the money could have been avoided.
Comment #153 August 13th, 2010 at 1:21 pm
@Richard Elwes
In a sense, you are of course right. The problem is that, in many articles, the perception generated is still the wrong one. Just one sentence at the end saying that in the coming days, (or weeks, or month, or whatever) the details will be checked won’t be noticed by many people. This leads to an avalanche of misinformation (well demonstrated by things my non-science friends told me in the last couple of days).
In any case, I think if you choose to report that “a proof has been offered, by a reputable researcher” you also have the obligation to report any new development that strongly suggests that something is wrong with the proof. Wouldn’t you agree?
Comment #154 August 13th, 2010 at 2:01 pm
I would like to second Gil’s question (#111), what would a world where P = PSPACE look like, beyond the revelations that would come from living in a world where P = NP, and the ability I would gain to play a perfect game of Reversi.
Comment #155 August 13th, 2010 at 2:05 pm
By the way, if Scott wanted to generate discussion about something else than his non-bet he should have not have phrased it to be about the ethics of scientific betting. It is pretty hard to see anything unethical with scientific betting in general.
A more interesting discussion is whether it would communicate any information. For the reasons stated by Gil and others I do not think betting would do much good in mathematics.
I could imagine that it could do some good in more empirical areas of science however. In medicine we might need an estimate of the danger or benefit of certain substances but opinion among scientists might be very conflicted. Prediction markets might in certain circumstances be a way to aggregate their opinions.
On the other hand, predictions markets might be taken to bias the scientists and thus impede the progress of science.
Comment #156 August 13th, 2010 at 3:12 pm
Scott’s coherent argument.
Vinay is not white.
Therefore his proof is not right.
Comment #157 August 13th, 2010 at 3:15 pm
I got 2 private comments about my comments on the bet by some distinguished colleagues: One wrote “By the way, I disagree with you regarding Scott’s bet- I found it very helpful in the initial confusion after the manuscript surfaced.”
I tried to respond: “Maybe you are right, but from now on, if a similar manuscript surface, gets some attention, and nobody will bet his house on it this will ADD to the confusion.” but the response for that was: “Due to Scott’s success, I predict that the next faulty manuscript will generate lots of bets. It is best to formalize this in a prediction market, so people who invest time to understand the paper can signal this by putting their money where their mouth is.” The other colleague referred (positively) to Scott’s bet as the “appropriate zionist reaction ” to VD’s paper.
Comment #158 August 13th, 2010 at 3:27 pm
My two cents about why people don’t use HOL and other provers and proof assistants:
1. When I am writing a paper I can *assume* lemmas that I think are true and continue my work and then return to checking them if I feel this is needed.
2. I can assume that the referee/reader know many theorems that I am using and I don’t need to state them nor prove them.
I haven’t seen proof assistants that allow me to do these things easily. I can write a very short informal proof that for every tree, if the label of each parent is larger than its children, then the root has the largest label. Proving this in a proof assistant is ridiculously difficult and time consuming and has taught me how inefficient it is to use them even for toy problems like this, let alone for a real result. It is like coding a 3D MMRPG in assembly, even worse! I am not going to use them for any real work until they advance to python level.
Comment #159 August 13th, 2010 at 4:03 pm
Scott’s coherent argument.
Vinay is not white.
Therefore his proof is not right.
Yes, that’s correct: anyone who knows me will tell you about how I racistly dismiss any advance in theoretical computer science made by individuals of Indian descent. (For example, the complexity class BQP, defined by my adviser Umesh Vazirani? Won’t touch it with a ten-foot pole.) This policy has the great advantage of shortening the STOC/FOCS proceedings from a phone book to a pamphlet.
Comment #160 August 13th, 2010 at 4:17 pm
Stil,
I think if you choose to report that “a proof has been offered, by a reputable researcher” you also have the obligation to report any new development that strongly suggests that something is wrong with the proof. Wouldn’t you agree?
Yes, I would agree with that. And so, it seems, would my occasional employers.
Comment #161 August 13th, 2010 at 4:34 pm
I would like to second Gil’s question (#111), what would a world where P = PSPACE look like, beyond the revelations that would come from living in a world where P = NP, and the ability I would gain to play a perfect game of Reversi.
Gil and Vadim: It’s a great question; sorry for taking so long to get around to it!
For me, one of the most exciting implications of P=PSPACE beyond P=NP would be that quantum mechanics could be efficiently simulated on a classical computer (i.e., P=BQP).
Another implication would be that P=P#P: that is, one could count the number of solutions to an NP-complete problem in polynomial time, which would in turn have lots of important implications for statistical physics.
Comment #162 August 13th, 2010 at 5:21 pm
@Vladimir Levin #21
I see what your saying, but whatever it was I read has my mind in this mode where it thinks that is just not applicable to this situation/is trivial. Could someone who has read the proof (even briefly) clarify what the strategy is?
My mind is relating this to a situation like:
in trying to prove A you show ~A -> 1+1=3 and conclude A. Then the analogy to our question is “why doesn’t this work for 2+2=3 or 2+2=5?”…it just doesn’t…~A didn’t imply that…and even if it did what matters? as long as its a contradiction
You could argue that maybe the similar properties of k-XORSAT make some similar property of it implied by P=NP. But even so, as long as the property is also a contradiction than the proof is possibly safe. Like I said, as far as my mind knows, he hasn’t said anything about the hardness of k-SAT, what class it is in, etc. Just that it has this property which we know it can’t.
Comment #163 August 13th, 2010 at 5:31 pm
@Scott #165
I can’t hear about P vs. BQP without thinking that it has strong connections to (or would benefit by being approached via) the various no-go theorems like Kochen-Specker, Bell, etc. that point out why quantum mechanics can’t be classical mechanics in disguise. I know these results don’t directly affect local computational “simulations”…but it still feels like they should have something to say about it…or maybe P≠BQP is a deserving no-go theorem in its own right!
For this reason P=BQP would really really shock me, since it would imply that classical physics can efficiently simulate quantum mechanics, yet couldn’t actually explain quantum mechanics…
Comment #164 August 13th, 2010 at 6:26 pm
I don’t want to hijack this conversation any further (and as a layman, I hate wasting experts’ time with my inconsequential questions), but I can’t wrap my head around BQP (possibly, likely?) being outside NP.
Isn’t factoring in NP, since checking whether the factors are correct is in P? Is it just a matter of factoring being in BQP ∩ NP, where we expect other problems that could be efficiently solved on a QTM to be BQP-complete, or am I (as usual) missing something very big?
Comment #165 August 13th, 2010 at 7:01 pm
@Richard Elwes
That is great. You are right; New Scientist seems to do a very good job.
Since you asked for an example of a “cringe-inducing” article… For instance, I found the ones from The Economic Times a bit problematic: see [1] (especially the title) and even worse [2].
Of course one can always point out a few bad examples. On average, I found the reporting on this issue surprisingly appropriate. It certainly seems better than what I remember from the “PRIMES is in P” result.
Comment #166 August 13th, 2010 at 10:45 pm
Isn’t factoring in NP, since checking whether the factors are correct is in P?
Factoring is not in NP just because it isn’t a yes-no question. However, it is in FNP (functional NP), which implies that any reasonable yes-no question derived from it is in both NP and coNP. For instance, whether a number has at least three prime factors.
It is true that since primality is in P, factoring is in FNP. However, that is a very advanced proof of the fact that factoring is in FNP. It was shown in the 70s that primality and factoring together are in NP/FNP. In order to show that p is prime, you can present (with a recursive certificate) a prime factorization of p-1, and a primitive residue mod p. You can confirm that the residue has order p-1 by exponentiating it to the power (p-1)/q for every prime factor q of p-1. The existence of this residue implies that p is prime. It is not hard to check that the tower of primes and certificates is polynomial in size. The certificates shrink appreciably at each stage because you can cast off factors of 2.
Comment #167 August 14th, 2010 at 1:21 am
Vadim P (#167):
I can’t wrap my head around BQP (possibly, likely?) being outside NP.
You’re right that factoring and discrete log, the most famous BQP problems, are also in NP intersect coNP. The difficulty is that, to prove BQP ⊆ NP, you’d have to give a general-purpose way to certify the output of any quantum computation via a succinct classical certificate (which a classical computer can easily check). At present, no one has any idea how to do that, and it might well be impossible. For more, see my BQP and the Polynomial Hierarchy paper.
Comment #168 August 14th, 2010 at 3:29 am
Professor Aaronson,
I suspect you’re getting a lot of comments from the outraged, above, and less from the people who aren’t outraged (or are grateful), so I’ll try to hop in on the latter scale.
I’d been busy and missed the initial “proof” announcement, so once I started looking for evaluations of it, your blog post was one of the first I found. It caused me to significantly discount the probability the proof was correct. So, thank you for that – I think “putting your money where you mouth is” is one of the best ways for signaling how firmly you believe something.
I would say, my main critique of the technique though, is the bias that it conceivably lends to *your* motives afterward. With such a large bet on the line, it seems inevitable that any human would have a lot of trouble objectively evaluating future evidence in the process. I know nothing about you, personally, and I certainly don’t mean to impugn you, personally. But I will honestly tell you that, while your bet (correctly, I think) caused me to discount the original proof substantially, it *also* caused me to substantially discount your subsequent criticism of it. In this case, that didn’t matter much (since many others are criticizing it, too), but I thought I’d provide clear feedback of that, since you seemed to be interested here in finding out more general principles from the results.
In any event, thanks again for taking the time to communicate with us on this topic, and for trying this experiment. I’ve found both useful and interesting.
Comment #169 August 14th, 2010 at 4:08 am
Stil,
You’re right – those are terrible! But, more generally, I stand by my objection to Scott’s characterisation of the recent media coverage as unremittingly irresponsible and awful, because I don’t think it has been.
Comment #170 August 14th, 2010 at 6:46 am
Don’t let the critics get to you. Your bet was exactly what more scientists should do, and not nasty or personal in any way that I can fathom. Scientists should express their opinion, and betting is a clear, credible, and quantitative way to express it. It would be as shame if the reaction caused you or others not to make similar bets in the future.
I just wish there were a central place to make bets on scientific claims and follow the odds in the vision of Robin Hanson, rather than every scientist having to declare their bet on their own individual blogs.
Comment #171 August 14th, 2010 at 4:15 pm
“The other colleague referred (positively) to Scott’s bet as the “appropriate zionist reaction ” to VD’s paper.”
Gil/Scott: Emm … what does that mean?
Comment #172 August 14th, 2010 at 4:26 pm
“First, the PTRS-B articles document that both high IQ’s and rigorous training serve well to create ingenious justifications for behaviors that are self-serving; thus intelligence and education provide less protection against irrationality than might be expected. Reinhard Selten’s memorable aphorism “Game theory is for proving theorems, not for playing games” reminds us that irrational motivations can be encoded even into mathematical postulates and axioms.
The encoding of essentially irrational motivations in axioms occurs in the sciences too: “So, what is quantum mechanics? It’s not a physical theory in the same sense as electromagnetism or general relativity: quantum mechanics is the operating system that other physical theories run on as application software” ”
@Sidles: This is so brilliant. I have often wondered about how my training and IQ is only helping me become more “evil” 😀 The QM as OS quote is fantastic.
Comment #173 August 14th, 2010 at 4:30 pm
Gil/Scott: Emm … what does that mean?
QTR: I have no real idea what it means either, but I laughed pretty hard at it.
For the record, while I support the continued existence of the State of Israel (and indeed was picking fresh persimmons on a kibbutz this afternoon), and also believe that any P≠NP proof will need to separate 3SAT from 2SAT and XORSAT, I fail to see a strong connection between the two.
Comment #174 August 14th, 2010 at 4:57 pm
Richard Elwes #172:
I stand by my objection to Scott’s characterisation of the recent media coverage as unremittingly irresponsible and awful, because I don’t think it has been.
No, you’re right, it hasn’t—I apologize if I seemed to imply as much! Some of it was bad, but by no means all.
Comment #175 August 14th, 2010 at 8:00 pm
scott,
i don’t think the problems with this particular bet was an ethical one but confusion in linking the strength of the conclusion and the reasons supporting it.The context of the situation as i see it is that after being ask for your opinion and 1) acknowledging the difficulty of rendering expert judgment on such a complicated issue in so short a time frame 2)admitted you hadn’t studied the manuscript 3)said you didn’t intend to until other expert opinion indicate that this was a good idea you then concluded by placing a $200,000 bet against the proof being correct and then said you were very serious about it.
the situation described in 1,2,3 above does not even hint as to how your conclusion was formed without a whole lot of speculation. that you think that the proof is incorrect is straightforward but what ought one to make of the $200,000 offer? it is obviously not rhetoric or hyberbole as this is contradicted by you saying that you are serious about it and the amount seems in line with that idea.it is also more than the usual token amounts typical for bets of this type and you seems to have reject some of the other approaches to giving an opinion such as sliding scale (see Comment #98), credibility intervals, etc.
if that is so then the amount sends a strong signal that you are strongly convinced of your conclusion without the benefit of a detail examination of the paper. this allows one to reasonable speculate that a) you really have good reasons to support the conclusion but choose to not say or hint at them b) there is something trivially wrong with the paper that other expert will pick upon explain more fully later c) you really have no good technical reasons at all to support your conclusion and so are motivated by other more personal reasons to draw this conclusion e.g. media attention, personal dislike etc.
Comment #176 August 14th, 2010 at 9:55 pm
#178
Don’t heckle Scott for having a different opinion. You can go ask the herd on the other websites why they bet that Vinay Deolalikar’s paper was more promising for public review than any of the other floating on the internet.
Comment #177 August 15th, 2010 at 5:24 am
Thanks Scott – sorry if I seem defensive! Not that the media are by any means perfect, but sometimes it can get unfairly scapegoated.
I’ve much enjoyed your commentary on this story (and the style with which you’ve handled some of your, erm, more excitable commenters).
Comment #178 August 15th, 2010 at 6:41 am
Richard Elwes,
I’m not sure if you’re aware of this precursor to the whole event
http://rjlipton.wordpress.com/2010/07/01/can-amateurs-solve-pnp/
Looks like Dick was trying to do shake things up on these lines after the events of the first prize March-June 2010.
Comment #179 August 15th, 2010 at 7:03 am
And Richard Elwes,
You’re a journalist, known to get excitable, don’t you and your pals go chasing after Vinay’s car in Silicon Valley!
Comment #180 August 16th, 2010 at 4:05 am
#146:
Thanks. However, are you sure it was Gauss’s cause? Did Newton, Copernicus, etc. use it or not?
And it still does not explain “why!”. Is it just a matter of nomenclature so that other people couldn’t understand it easily?
Comment #181 August 16th, 2010 at 11:24 am
@Justin Dove 162
I think you’re right. I am not a mathematician so I am not sure exactly how these objections are breaking down. I think it may be nice for someone “in the know” to provide an outline of Vinay’s proof “for dummies” that just includes the core logical steps without any difficult mathematical detail (perhaps it’s been done and I missed it) along with the objections – at the same level of detail – and how they fit. My sense from reading this blog and rjlipton’s blog is that these objections around these similar problems in P are a good “sanity check” that a proof should pass before people take it seriously. In other words they expect the proof to explain things about the P vs. NP problem. Right now I am not in a position to make a serious effort to read this stuff, but I think if you read rjlipton’s blog maybe you’ll get the gut-level sense of what’s going on you’re looking for. There do seem to be some good discussions and summaries, but I can’t go back to look at them carefully myself to see if and how they address your question. Sorry about that!
Comment #182 August 16th, 2010 at 1:28 pm
PS: My impression is that the proof somehow exploits the special structure of ksat, but if xorsat has this structure as well, then evidently the proof would not be valid. As I said, if your interpretation of the basic logic is right, then it sounds as if your objection is sound…
Comment #183 August 17th, 2010 at 1:00 am
@Scott 173:
Oh well. I was hoping you or Gil would share the inside jewish joke. And I don’t see how it’s possible to laugh so hard without knowing what it means …. ? :-/
Anyway … I suppose it’s best to avoid any more controversy.
Comment #184 August 17th, 2010 at 6:12 am
QTR: Dunno about you, but I’ve laughed at plenty of jokes without really understanding them!
I’m guessing that Gil’s anonymous colleague was using “Zionist” as shorthand for: “taking justice into your own hands; doing what you see as the right and necessary thing even if most of the world condemns it and even some of your friends are embarrassed by it.” But I’m not sute — maybe Gil (or his colleague) could clarify for us.
Comment #185 August 17th, 2010 at 8:15 am
Scott,
It may be that the mob is eventually going to blame you if Vinay Deolalikar’s proof does not work. The mob will strongly believe that you somehow jinxed his proof by betting against it. Aah, the perils of mob science.
Comment #186 August 17th, 2010 at 8:18 am
You used your quantum knowledge and powers to change the bits of the pdf AFTER it was released by Vinay Deolalikar. You’re a witch, Scott!
Comment #187 August 17th, 2010 at 8:38 am
The soon upcoming version will pacify the mob!
Comment #188 August 17th, 2010 at 9:57 am
Dear Dr Scott Aaronson,
An academic researcher myself, I would just like to send you a brief support.
I think there is nothing wrong in what you did. In fact, partly because your bet, the claimed proof has drawn a lot more attention beyond the computer science community, which has to a degree educated the general public what computer science is truly about.
On the ethics side, to me, you just expressed, in an interesting way, your disbelief on the proof and your understanding of the problem difficulty.
There is perhaps no need to continue the debate on this. Time will dilute everything. In the years to come and particularly when the P vs NP problem is finally resolved, both Dr Deolalikar’s effort and your bet will be appreciated as interesting pieces of the history.
Comment #189 August 17th, 2010 at 10:22 am
Richard Elwes, You’ve disappeared, please come back. Don’t take offense at our jokes.
Comment #190 August 17th, 2010 at 3:42 pm
Just found this quote from E Rutherford: ““You should never bet against anything in science at odds of more than about 10-12 to 1 against”. Scott, now you share something with Einstein (http://thinkexist.com/quotation/anyone_who_expects_a_source_of_power_from_the/191140.html)
More funny yet (because some starts to think in terms of war of bands) this quote can be found on rjliptons webpage 😀
Comment #191 August 17th, 2010 at 5:30 pm
Quantum Tennis Referee Says: @Sidles: … The “QM as OS” quote is fantastic.
The remark “quantum mechanics is the operating system that other physical theories run on as application software” can be found in Scott’s Quantum computing since Democritus #9 … a lecture series that I sincerely admire and recommend (even though I don’t agree with everything in it).
QTR, you can take the work “sincerely” for granted, because writing “funny” is completely beyond my talents.
Moreover, during the past week, the Deolalikar episode has amply demonstrated that writing high-quality sardonicism is even tougher than writing “funny” … requiring Joseph-Heller levels of narrative talent (at a minimum).
IMHO no-one to date has successfully written sardonically about the Deolalikar’s claimed proof (despite numerous attempts) … in fact, no attempt has even come close.
Perhaps more folks need to keep in-mind that (IMHO) Heller’s Catch-22 worked as a masterpiece of sardonicism only because at the end, Orr *did* get to Sweden.
Comment #192 August 19th, 2010 at 4:55 am
@Scott:
“the mathematicians and scientists I admired most were never those who withdrew from the world, but rather those (like Bertrand Russell and Carl Sagan) who tried as hard as possible to change it.”
That is a nice thought, and I do think you are changing the world with your work.
But this comment has not much to do with the question we were discussing when I wrote the comment, namely your bet, and the attention it brought to you and the light is shed on VDs work.
Comment #193 August 20th, 2010 at 5:33 am
#192 Forget about VD man! He has had enough attention already! Go start a VD fan club or something on your own stupid blog!
Comment #194 August 20th, 2010 at 9:39 pm
Using basic probability and advanced guessology, I’ve concluded that you assigned a 0.5% probability of correctness to VD’s paper. Thanks for stating your opinion so clearly. Details here.
PS: A posteriori, I wonder if 0.5 % isn’t rather on the high side. After all, it means that we only have to wait for 137 more papers of similar quality to have a 50 % chance of having a solution to P vs NP.