{"id":458,"date":"2010-08-13T21:08:28","date_gmt":"2010-08-14T01:08:28","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=458"},"modified":"2010-08-13T21:08:28","modified_gmt":"2010-08-14T01:08:28","slug":"eight-signs-a-claimed-p%e2%89%a0np-proof-is-wrong","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=458","title":{"rendered":"Eight Signs A Claimed P\u2260NP Proof Is Wrong"},"content":{"rendered":"

As of this writing, Vinay Deolalikar still hasn’t retracted his P\u2260NP claim, but a clear consensus has emerged that the proof, as it stands, is fatally flawed.\u00a0 The first reason is that we’re not going to separate k-SAT from much easier problems purely by looking at the structure of the solution space: see for example this comment<\/a> by Ryan Williams.\u00a0 The second reason is that, independently of the solution-space issue, Neil Immerman has identified critical flaws<\/a> in the finite model theory part of the paper.<\/p>\n

The researchers who actually studied Deolalikar’s paper, thought hard about it, and figured out in a matter of days why it doesn’t work deserve our undying gratitude (they certainly have mine!).\u00a0 At the same time, if someday we have a P\u2260NP claim at this level several times per year—which I see as entirely possible—then it’s clear that the sort of heroic effort we saw over the last week isn’t going to scale.\u00a0 And thus, several commenters wanted to know how someone as lazy as I am could nevertheless be so confident in predicting what would happen:<\/p>\n

Would you enlighten us as to what was the PROCESS behind your quick and correct judgment? … 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?<\/p>\n

Scott Aaronsohn [sic], 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!<\/p><\/blockquote>\n

While it pains me to say so, these commenters give me way too much credit.\u00a0 The truth, as far as I can tell, is that many (most?) complexity theorists reached exactly the same conclusion as I did and just as quickly; it’s just that most (with some notable exceptions) were too cautious to say so in public.\u00a0 Among those who did<\/em> comment publicly, the tendency was to bend over backwards to give Deolalikar the benefit of the doubt—an approach that I considered taking as well, until I imagined some well-meaning economist or physicist reading my generous words and coming away with the impression that P\u2260NP must be either licked or else hanging by a thread, and at any rate couldn’t have been nearly<\/em> as hard as all those computer scientists made it out to be.<\/p>\n

So, in the future, how can you<\/em> decide whether a claimed P\u2260NP proof is worth reading?\u00a0 I’ll now let you in on my magic secrets (which turn out not to be magic or secret at all).<\/p>\n

The thing not<\/em> to do is to worry about the author’s credentials or background.\u00a0 I say that not only for ethical reasons, but also because there are too many cases in the history of mathematics where doing so led to catastrophic mistakes.\u00a0 Fortunately, there’s something else you can do that’s almost<\/em> as lazy: scan the manuscript, keeping a mental checklist for the eight warning signs below.<\/p>\n

    \n
  1. The author can’t immediately explain why the proof fails for 2SAT, XOR-SAT, or other slight variants of NP-complete problems that are known to be in P.\u00a0 Historically, this has probably been the single most important “sanity check” for claimed proofs of P\u2260NP: in fact, I’m pretty sure that every attempt I’ve ever seen has been refuted by it.<\/li>\n
  2. The proof doesn’t “know about” all known techniques for polynomial-time algorithms, including dynamic programming, linear and semidefinite programming, and holographic algorithms.\u00a0 This is related to sign 1, but is much more stringent.\u00a0 Mulmuley’s GCT program is the only approach to P vs. NP I’ve seen that even has serious aspirations to “know about” lots of nontrivial techniques for solving problems in P (at the least, matching and linear programming).\u00a0 For me, that’s probably the single strongest argument in GCT’s favor.<\/li>\n
  3. The paper doesn’t prove any weaker results along the way: for example, P\u2260PSPACE, NEXP\u2284P\/poly, NP\u2284TC0<\/sup>, permanent not equivalent to determinant by linear projections, SAT requires superlinear time … P vs. NP is a staggeringly hard problem, which one should think of as being dozens<\/em> of steps beyond anything that we know how to prove today.\u00a0 So then the question arises: forget steps 30 and 40, what about steps 1, 2, and 3?<\/li>\n
  4. Related to the previous sign, the proof doesn’t encompass the known<\/em> lower bound results as special cases.\u00a0 For example: where, inside this proof, are the known lower bounds against constant-depth circuits?\u00a0 Where’s Razborov’s lower bound against monotone circuits?\u00a0 Where’s Raz’s lower bound against multilinear formulas?\u00a0 All these things (at least the uniform versions of them) are implied by P\u2260NP, so any proof of P\u2260NP should imply them as well.\u00a0 Can we see more-or-less explicitly why it does so?<\/li>\n
  5. The paper lacks the traditional lemma-theorem-proof structure.\u00a0 This sign was pointed out (in the context of Deolalikar’s paper) by Impagliazzo.\u00a0 Say what you like about the lemma-theorem-proof structure, there are excellent reasons why it’s used—among them that, exactly like modular programming, it enormously speeds up the process of finding bugs.<\/li>\n
  6. The paper lacks a coherent overview, clearly explaining how and why it overcomes the barriers that foiled previous attempts.\u00a0 Unlike most P\u2260NP papers, Deolalikar’s does<\/em> have an informal overview (and he recently released a separate synopsis<\/a>).\u00a0 But reading the overview felt like reading Joseph Conrad’s Heart of Darkness<\/em>: I’d reread the same paragraph over and over, because the words would evaporate before they could stick to my brain.\u00a0 Of course, maybe that just means I was too dense to understand the argument, but the fact that I couldn’t form a mental image of how the proof was supposed to work wasn’t a promising sign.<\/li>\n
  7. The proof hinges on subtle issues in descriptive complexity.\u00a0 Before you reach for your axes: descriptive complexity is a beautiful part of TCS, full of juicy results and open problems, and I hope that someday it might even prove useful for attacking the great separation questions.\u00a0 Experience has shown, however, that descriptive complexity also a powerful tool for fooling yourself into thinking you’ve proven things that you haven’t.\u00a0 The reason for this seems to be that subtle differences in encoding schemes—for example, whether you do or don’t have an order relation—can correspond to huge<\/em> differences in computational complexity.\u00a0 As soon as I saw how heavily Deolalikar’s proof relied on descriptive complexity, I guessed that he probably made a mistake in applying the results from that field that characterize complexity classes like P in terms of first-order logic.\u00a0 I’m almost embarrassed to relate this guess, given how little actual understanding went to it.\u00a0 Intellectual honesty does, however, compel me to point out that it was correct.<\/li>\n
  8. Already in the first draft, the author waxes philosophical about the meaning of his accomplishment, profusely thanks those who made it possible, etc.\u00a0 He says things like, “confirmations have already started arriving.”\u00a0 To me, this sort of overconfidence suggests a would-be P\u2260NP prover who hasn’t yet grasped the sheer number of mangled skeletons and severed heads that line his path.<\/li>\n<\/ol>\n

    You might wonder: if I had all these more-or-less articulable reasons for doubting Deolalikar’s proof, then why didn’t I just state<\/em> my reasons in the first place, instead of placing a $200,000 wager?<\/p>\n

    Well, I probably should<\/em> have stated the reasons.\u00a0 I apologize for that.<\/p>\n

    The best one can say about the lazy alternative I chose is that it led to a somewhat-interesting socio-mathematical experiment.\u00a0 By putting my life savings on the line, could I give the world a dramatic demonstration of just how high the stakes are with P vs. NP—that when computer scientists say this problem won’t be solved without a titanic advance in human knowledge, without overcoming obstacles like the ones mentioned in points 1-4 above, they’re not kidding?<\/em>\u00a0 After such a demonstration, would more people get it?\u00a0 Would they refrain from leaping out of their chairs at the next P vs. NP announcement?\u00a0 Like Richard Dawkins staring unflinchingly<\/a> at a steel pendulum swinging toward his face (which he knows has enough potential energy to almost<\/em> hit him but not quite), would they remember that the only miracle in life is that there are<\/em> no miracles, neither in mathematics nor in anything else?<\/p>\n

    I don’t know how well the experiment succeeded.<\/p>\n

    \n

    Update (8\/14):<\/font><\/strong> Somehow I completely forgot, over the course of the last three posts, to link to the PowerPoint talk Has There Been Progress on the P vs. NP Question?<\/a>, which has lots of relevant material about why it’s so hard to prove P\u2260NP and how to evaluate proposed attempts.\u00a0 Thanks to several commenters for correcting my oversight—I’ll try to give the author of those slides proper credit in the future!<\/p>\n","protected":false},"excerpt":{"rendered":"

    As of this writing, Vinay Deolalikar still hasn’t retracted his P\u2260NP claim, but a clear consensus has emerged that the proof, as it stands, is fatally flawed.\u00a0 The first reason is that we’re not going to separate k-SAT from much easier problems purely by looking at the structure of the solution space: see for example […]<\/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-458","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\/458","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=458"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/458\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=458"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=458"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=458"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}