{"id":3095,"date":"2017-01-03T20:56:04","date_gmt":"2017-01-04T01:56:04","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=3095"},"modified":"2019-01-28T14:26:55","modified_gmt":"2019-01-28T20:26:55","slug":"my-116-page-survey-article-on-p-vs-np-better-late-than-never","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=3095","title":{"rendered":"My 116-page survey article on P vs. NP: better late than never"},"content":{"rendered":"

For those who just want the survey itself, not the backstory, it’s here<\/a>. (Note:<\/i> Partly because of the feedback I’ve gotten on this blog, it’s now expanded to 121 pages!)<\/p>\n

\n

Update (Jan. 23)<\/font><\/b> By request, I’ve prepared a Kindle-friendly edition<\/a> of this P vs. NP survey—a mere 260 pages!<\/p>\n

\n

Two years ago, I learned that John Nash—that<\/em> John Nash—was, together with Michail Rassias, editing a volume about the great open problems in mathematics.  And they wanted me to write the chapter about the P versus NP question—a question that Nash himself had come close to raising, in a prescient handwritten letter<\/a> that he sent to the National Security Agency in 1955.<\/p>\n

On the one hand, I knew I didn’t have time for such an undertaking, and am such a terrible procrastinator that, in both<\/em> previous<\/a> cases<\/a> where I wrote a book chapter, I singlehandedly delayed the entire volume by months.  But on the other hand, John Nash.<\/p>\n

So of course I said yes.<\/p>\n

What followed was a year in which Michail sent me increasing panicked emails (and then phone calls) informing me that the whole volume was ready for the printer, except<\/em> for my P vs. NP thing, and is there any chance I’ll have it by the end of the week?  Meanwhile, I’m reading yet more papers about Karchmer-Wigderson games, proof complexity, time\/space tradeoffs, elusive functions, and small-depth arithmetic circuits.  P vs. NP, as it turns out, is now a big<\/em> subject.<\/p>\n

And in the middle of it, on May 23, 2015, John Nash and his wife Alicia were tragically killed on the New Jersey Turnpike, on their way back from the airport (Nash had just accepted the Abel Prize in Norway), when their taxi driver slammed into a guardrail.<\/p>\n

But while Nash himself sadly wouldn’t be alive to see it, the volume was still going forward.  And now we were effectively honoring Nash’s memory, so I definitely<\/em> couldn’t pull out.<\/p>\n

So finally, last February, after more months of struggle and delay, I sent Michail what I had, and it duly appeared in the volume Open Problems in Mathematics<\/a>.<\/p>\n

But I knew I wasn’t done: there was still sending my chapter out to experts to solicit their comments.  This I did, and massively-helpful feedback started pouring in, creating yet more work for me.  The thorniest section, by far, was the one about Geometric Complexity Theory (GCT)<\/a>: the program, initiated by Ketan Mulmuley and carried forward by a dozen or more mathematicians, that seeks to attack P vs. NP and related problems using a fearsome arsenal from algebraic geometry and representation theory.  The experts told me, in no uncertain terms, that my section on GCT got things badly wrong—but they didn’t agree with each other about how<\/em> I was wrong.  So I set to work trying to make them happy.<\/p>\n

And then I got sidetracked with the move to Austin and with other projects, so I set the whole survey aside: a year of sweat and tears down the toilet.  Soon after that, B\u00fcrgisser, Ikenmeyer, and Panova proved a breakthrough “no-go” theorem<\/a>, substantially changing the outlook for the GCT program, meaning yet more work for me if and when I ever returned to the survey.<\/p>\n

Anyway, today, confined to the house with my sprained ankle, I decided that the perfect was the enemy of the good, and that I should just finish<\/em> the damn survey and put it up on the web, so readers can benefit from it before the march of progress (we can hope!) renders it totally obsolete.<\/p>\n

So here it is!<\/a>  All 116 pages, 268 bibliography entries, and 52,000 words.<\/p>\n

For your convenience, here’s the abstract:<\/p>\n

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science.  Here I survey the status of this problem in 2017, for a broad audience of mathematicians, scientists, and engineers.  I offer a personal perspective on what it’s about, why it’s important, why it’s reasonable to conjecture that P\u2260NP is both true and provable, why proving it is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century toward solving those problems.  The discussion of progress includes diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.<\/p>\n

Thanks so much to everyone whose feedback helped improve the survey.  If you have additional feedback, feel free to share in the comments section!  My plan is to incorporate the next<\/em> round of feedback by the year 2100, if not earlier.<\/p>\n

\n

Update (Jan. 4)<\/b><\/span> Bill Gasarch writes to tell me that Lazslo Babai has posted an announcement scaling back<\/a> his famous “Graph Isomorphism in Quasipolynomial Time” claim. Specifically, Babai says that, due to an error discovered by Harald Helfgott, his graph isomorphism algorithm actually runs in about 22^O(\u221alog(n))<\/sup> time, rather than the originally claimed npolylog(n)<\/sup>. This still beats the best previously-known running time for graph isomorphism (namely, 2O(\u221a(n log n))<\/sup>), and by a large margin, but not quite as large as before.<\/p>\n

Babai pointedly writes:<\/p>\n

I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers.<\/p><\/blockquote>\n

Alas, my own experience has taught me the hard way that, on the Internet, it is do or do not. There is no disclaim.<\/p>\n

In any case, I’ve already updated my P vs. NP survey to reflect this new development.<\/p>\n

\n

Another Update (Jan. 10)<\/span><\/b> For those who missed it, Babai has another update<\/a> saying that he’s fixed the problem, and the running time of his graph isomorphism algorithm is back to being quasipolynomial.<\/p>\n

\n

Update (Jan. 19):<\/span><\/b> This moment—the twilight of the Enlightenment, the eve of the return of the human species back to the rule of thugs—seems like as good a time as any to declare my P vs. NP survey officially done<\/b>. I.e., thanks so much to everyone who sent me suggestions for additions and improvements, I’ve implemented pretty much all of them, and I’m not seeking additional suggestions!<\/p>\n","protected":false},"excerpt":{"rendered":"

For those who just want the survey itself, not the backstory, it’s here. (Note: Partly because of the feedback I’ve gotten on this blog, it’s now expanded to 121 pages!) Update (Jan. 23) By request, I’ve prepared a Kindle-friendly edition of this P vs. NP survey—a mere 260 pages! Two years ago, I learned that John […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","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,"jetpack_post_was_ever_published":false},"categories":[5],"tags":[],"class_list":["post-3095","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\/3095","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3095"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3095\/revisions"}],"predecessor-version":[{"id":4090,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3095\/revisions\/4090"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3095"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3095"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3095"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}