{"id":1293,"date":"2013-04-02T13:25:17","date_gmt":"2013-04-02T18:25:17","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1293"},"modified":"2017-01-12T16:34:33","modified_gmt":"2017-01-12T21:34:33","slug":"two-p-vs-np-updates-neither-of-them-technical","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1293","title":{"rendered":"Two P vs. NP updates (neither of them technical)"},"content":{"rendered":"
\"lilymeme\"<\/a>

“Meme” courtesy of my brother David<\/p><\/div>\n

First news item: it’s come to my attention that yesterday, an MIT professor abused his power over students for a cruel April Fools’ Day prank involving the P vs. NP problem.\u00a0 His email to the students is below.<\/p>\n

I assume most of you already heard the news that a Caltech grad student, April Felsen, announced a 400-page proof of P\u2260NP last week.\u00a0 While I haven’t yet completely digested the argument, it’s already clear that Felsen (who I actually knew back when she was an MIT undergrad) has changed theoretical computer science forever, bringing in new tools from K-theory to higher topos theory to solve the biggest problem there was.<\/p>\n

Alas, Felsen’s proof has the “short-term” effect of making the existing 6.045 seem badly outdated.\u00a0 So, after long reflection, I’ve made a decision that not all of you are going to like, but that I believe is the right one intellectually.\u00a0 I’ve decided to reorient the entire course to focus on Felsen’s result, starting with tomorrow’s lecture.<\/p>\n

And further, I decided to rewrite Thursday’s midterm to focus almost entirely on this new material.\u00a0 That means that, yes, you’re going to have THREE DAYS to learn at least the basics of algebraic topology and operator algebras, as used in Felsen’s proof.\u00a0 To do that, you might need to drop everything else (including sleep, unfortunately), and this might prove to be the most strenuous and intense thing you’ve ever done.\u00a0 But it will also be an experience that will enrich your minds and ennoble your souls, and that you’ll be proud to tell your grandchildren about.\u00a0 And of course we’ll be there to help out.\u00a0 So let’s get started!<\/strong><\/p>\n

All the best,
\nScott<\/p>\n

\n

Second news item: many of you have probably heard that Lance Fortnow’s The Golden Ticket<\/a><\/em>—the first popular book about the P vs. NP problem—is now out.\u00a0 (The title refers to Roald Dahl’s Charlie and the Chocolate Factory<\/em>, which involved a few chocolate bars that had coveted golden tickets inside the wrappers, along with millions of chocolate bars that didn’t.)\u00a0 I read it last week, and I think it’s excellent: a book I’ll happily recommend to family and friends who want the gentlest introduction to complexity theory that exists.<\/p>\n

Some context: for more than a decade, people have been telling me that I<\/em> should write a popular book about P vs. NP, and I never did, and now Lance has.\u00a0 So I’m delighted to say that reading Lance’s book quickly cured me of any regrets I might have felt.\u00a0 For not only is The Golden Ticket<\/em> a great book, but better yet, it’s not a book that I ever could’ve written.<\/p>\n

Here’s why: every time<\/em> I would have succumbed to the temptation to explain something too complicated for the world’s journalists, literary humanists, and pointy-haired bosses—something like relativization, or natural proofs, or arithmetization, or Shannon’s counting argument, or Ladner’s Theorem, or coNP, or the reasons to focus on polynomial time—every time, Lance somehow manages to resist the temptation, and to stick to cute stories, anecdotes, and practical applications.\u00a0 This is really, truly a popular<\/em> book: as Lance points out himself, in 162 pages of discussing the P vs. NP question, he never even formally defines P and NP!<\/p>\n

But it goes beyond that: in the world of The Golden Ticket<\/em>, P vs. NP is important because, if P=NP, then people could design more effective cancer therapies, solve more crimes, and better predict which baseball games would be closely-matched and exciting (yes, really).\u00a0 P vs. NP is also important because it provides a unifying framework for understanding current technological trends, like massively-parallel computing, cloud computing, big data, and the Internet of things.\u00a0 Meanwhile, quantum computing might or might not be possible in principle, but either way, it’s probably not that relevant because it won’t be practical for a long time.<\/p>\n

In short, Lance has written precisely<\/em> the book about P vs. NP that the interested layperson or IT professional wants and needs, and precisely<\/em> the book that I couldn’t have written.\u00a0 I would’ve lost patience by around page 20, and exclaimed:<\/p>\n

“You want me to justify the P vs. NP problem by its relevance to baseball??<\/em>\u00a0 Why shouldn’t baseball<\/em> have to justify itself by its relevance to P vs. NP?\u00a0 Pshaw!\u00a0 Begone from the house of study, you cretinous fools, and never return!”<\/strong><\/p>\n

My favorite aspect of The Golden Ticket<\/em> was its carefully-researched treatment of the history of the P vs. NP problem in the 50s, 60s, and 70s, both in the West and in the Soviet Union (where it was called the “perebor” problem).\u00a0 Even complexity theorists will learn countless tidbits—like how Leonid Levin was “discovered” at age 15, and how the powerful Sergey Yablonsky stalled Soviet perebor<\/em> research by claiming to have solved the problem when he’d done nothing of the kind.\u00a0 The historical chapter (Chapter 5) is alone worth the price of the book.<\/p>\n

I have two quibbles.\u00a0 First, throughout the book, Lance refers to a hypothetical world where P=NP as the “Beautiful World.”\u00a0 <\/em>I would’ve called that world the “Hideous World”!\u00a0 For it’s a world where technical creativity is mostly worthless, and where the mathematical universe is boring, flat, and incomprehensibly comprehensible.\u00a0 Here’s an analogy: suppose a video game turned out to have a bug that let you accumulate unlimited points just by holding down a certain button.\u00a0 Would anyone call that game the “Beautiful Game”?<\/p>\n

My second disagreement concerns quantum computing.\u00a0 Overall, Lance gives an admirably-accurate summary, and I was happy to see him throw cold water on breathless predictions about QC and other quantum-information technologies finding practical applications in the near future.\u00a0 However, I think he goes beyond the truth when he writes:<\/p>\n

[W]e do not know how to create a significant amount of entanglement in more than a handful of quantum bits.\u00a0 It might be some fundamental rule of nature that prevents significant entanglement for any reasonable length of time.\u00a0 Or it could just be a tricky engineering problem.\u00a0 We’ll have to let the physicists sort that out.<\/p>\n

The thing is, physicists do<\/em> know how to create entanglement among many thousands or even millions of qubits—for example, in condensed-matter systems like spin lattices, and in superconducting Josephson junctions.\u00a0 The problem is “merely” that they don’t know how to control<\/em> the entanglement in the precise ways needed for quantum computing.\u00a0 But as with much quantum computing skepticism, the passage above doesn’t seem to grapple with just how hard it is<\/em> to kill off scalable QC.\u00a0 How do you cook up a theory that can account for the massively-entangled states that have already been demonstrated, but that doesn’t<\/em> give you all of BQP<\/a>?<\/p>\n

But let me not harp on these minor points, since The Golden Ticket<\/em> has so many pleasant features.\u00a0 One of them is its corny humor: even in Lance’s fantasy world where a proof of P=NP has led to a cure for cancer, it still<\/em> hasn’t led to a cure for the common cold.\u00a0 Another nice feature is the book’s refreshing matter-of-factness: Lance makes it clear that he believes that<\/p>\n

(a) P\u2260NP,
\n(b) the conjecture is provable but won’t<\/em> be proven in the near future, and
\n(c) if we ever meet an advanced extraterrestrial civilization, they’ll also have asked the P vs. NP question or something similar to it.<\/p>\n

Of course we can’t currently prove<\/em> any of the above statements, just like we can’t prove the nonexistence of Bigfoot.\u00a0 But Lance refuses to patronize his readers by pretending to harbor doubts that he quite reasonably doesn’t.<\/p>\n

In summary, if you’re the sort of person who stops me in elevators to say that you like my blog even though you never actually understand anything in it, then stop reading Shtetl-Optimized<\/em> right now and go read Lance’s book<\/a>.\u00a0 You’ll understand it and you’ll enjoy it.<\/p>\n

And now it’s off to class, to apologize for my April Fools prank and to teach the Cook-Levin Theorem.<\/p>\n","protected":false},"excerpt":{"rendered":"

First news item: it’s come to my attention that yesterday, an MIT professor abused his power over students for a cruel April Fools’ Day prank involving the P vs. NP problem.\u00a0 His email to the students is below. I assume most of you already heard the news that a Caltech grad student, April Felsen, announced […]<\/p>\n","protected":false},"author":1,"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_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-1293","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1293","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=1293"}],"version-history":[{"count":10,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1293\/revisions"}],"predecessor-version":[{"id":1536,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1293\/revisions\/1536"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}