{"id":456,"date":"2010-08-09T02:53:58","date_gmt":"2010-08-09T06:53:58","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=456"},"modified":"2010-08-09T02:53:58","modified_gmt":"2010-08-09T06:53:58","slug":"putting-my-money-where-my-mouth-isnt","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=456","title":{"rendered":"Putting my money where my mouth isn’t"},"content":{"rendered":"

A few days ago, Vinay Deolalikar<\/a> of HP Labs started circulating a claimed proof of P\u2260NP<\/a>.\u00a0 As anyone could predict, the alleged proof has already been Slashdotted<\/a> (see also Lipton’s blog<\/a> and Bacon’s blog<\/a>), and my own inbox has been filling up faster than the Gulf of Mexico.<\/p>\n

Alas, a simple “top kill” seems unlikely to work here.\u00a0 What’s obvious from even a superficial reading is that Deolalikar’s manuscript is well-written, and that it discusses the history, background, and difficulties of the P vs. NP question in a competent way.\u00a0 More importantly (and in contrast to 98% of claimed P\u2260NP proofs), even if this attempt fails, it seems to introduce some thought-provoking new ideas, particularly a connection between statistical physics and the first-order logic characterization of NP.\u00a0 I’ll leave it to the commenters to debate whether Deolalikar’s paper exhibits one or more of the Ten Signs A Claimed Mathematical Breakthrough Is Wrong<\/a>.<\/p>\n

“But enough question-dodging!” you exclaim.\u00a0 “Is the proof right or isn’t it?\u00a0 C’mon, it’s been like three hours<\/em> since you first saw it—what’s taking you so long?”\u00a0 Well, somehow, I haven’t yet found the opportunity to study this 103-page manuscript in detail.\u00a0 Furthermore, I don’t plan to interrupt my vacation time in Israel and Greece to do so, unless<\/em> experts who have<\/em> studied the paper in detail start telling me that I should.<\/p>\n

Unfortunately, I can already foresee that the above response will fail to staunch the flow of emails.\u00a0 As a blogger, I’m apparently expected to<\/p>\n

(1) render an instantaneous opinion on any claimed mathematical breakthrough,<\/p>\n

(2) be consistently right, and<\/p>\n

(3) do the above without<\/em> looking like I’m being unfair or rushing to judgment.<\/p>\n

While requirements (1) and (2) are not so<\/em> hard to satisfy simultaneously, (3) makes my job an extremely difficult one.\u00a0 In fact, I could think of only one mechanism to communicate my hunch about Deolalikar’s paper in a way that everyone would agree is (more than) fair to him, without<\/em> having to invest the hard work to back my hunch up.\u00a0 And thus I hereby announce the following offer:<\/p>\n

If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P\u2260NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.<\/em><\/strong><\/p>\n

I’m dead serious—and I can afford it about as well as you’d think I can.<\/p>\n

Update (August 10):<\/font><\/strong> One whole day into this saga, Dick Lipton and Ken Regan have written a detailed post<\/a> setting out four possible problems that have already been identified in the proof, and which the ball is now in Deolalikar’s court to address.\u00a0 Kudos to Dick, Ken, and numerous commenters for actually digging into the paper (unlike some lazier folks I could name \ud83d\ude42 ).<\/p>\n

Another Update:<\/font><\/strong> Since some journalists seem (unbelievably) to have missed the point<\/a> of this post, let me now state the point as clearly as I can.\u00a0 The point is this: I really, really<\/strong> doubt that Deolalikar’s proof will stand.\u00a0 And while I haven’t studied his long, interesting paper in detail and pinpointed the irreparable flaw, something deep inside me rebels against the charade of “keeping an open mind,” when long experience with competent but ultimately unsuccessful proof attempts allows me to foresee perfectly well how things are going to play out here.\u00a0 I would make a terrible trial court judge: ten minutes into the proceedings, I’d be screaming, “The defendant obviously did it!\u00a0 I sentence him to death!”\u00a0 Fortunately I’m not<\/strong> a judge, and I have a way of stating my prediction that no reasonable person could hold against me: I’ve literally bet my house on it.<\/em><\/p>\n

Yet Another Update:<\/font><\/strong> What’s emerged as the perhaps central issue is the bane of so many attempted P\u2260NP 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?<\/em> If Deolalikar can’t provide a clear and convincing answer to that question, the proof is toast.<\/p>\n","protected":false},"excerpt":{"rendered":"

A few days ago, Vinay Deolalikar of HP Labs started circulating a claimed proof of P\u2260NP.\u00a0 As anyone could predict, the alleged proof has already been Slashdotted (see also Lipton’s blog and Bacon’s blog), and my own inbox has been filling up faster than the Gulf of Mexico. Alas, a simple “top kill” seems unlikely […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[5],"tags":[],"class_list":["post-456","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/456","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=456"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/456\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=456"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=456"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}