A reader named Darren commented on my last post:<\/p>\n
I have this feeling that this whole P and NP thing is not only a profound problem that needs solving, but something that can be infinitely curious to try and wrap your mind around\u2026<\/p>\n
Thing is- there\u2019s a whole world of great minded, genius hackers out here that can\u2019t understand one iota of what anyone is talking about. We\u2019re not your traditional code-savvy hackers; we\u2019re your inventors, life hackers, researchers, scientists\u2026 and I think I can speak for most of us when I say: We would love to take the time to really dive into this thread, but we ask that someone (you) write a blog that breaks this whole thing down into a rest-of-the-world-friendly P\/NP for dummies\u2026 or at least explain it to us like we\u2019re stupid as hell\u2026 at this point I\u2019m really okay with even that.<\/p><\/blockquote>\n
I’m<\/em> of course the stupid one here, for forgetting the folks like Darren who were enticed by L’Affaire Deolalikar into entering our little P\/NP tent, and who now want to know what it is we’re hawking.<\/p>\n
The short answer is: the biggest unsolved problem of theoretical computer science, and one of the deepest questions ever asked by human beings!\u00a0 Here are four informal interpretations of the P vs. NP problem that people give, and which I can endorse as capturing the spirit of what’s being asked:<\/p>\n
\n
- Are there situations where brute-force search<\/em>—that is, trying an exponential number of possibilities one-by-one, until we find a solution that satisfies all the stated constraints—is essentially the best algorithm possible?<\/li>\n
- Is there a fast algorithm to solve the NP-complete problems<\/em>—a huge class of combinatorial problems that includes scheduling airline flights, laying out microchips, optimally folding proteins, coloring maps, packing boxes as densely as possible, finding short proofs of theorems, and thousands of other things that people in fields ranging from AI to chemistry to economics to manufacturing would like to solve?\u00a0 (While it’s not obvious a priori<\/em>, it’s known that these problems are all “re-encodings” of each other.\u00a0 So in particular, a fast algorithm for any one of the problems would imply fast algorithms for the rest; conversely, if any one of them is hard then then they all are.)<\/li>\n
- Is it harder to solve a math problem yourself than to check a solution by someone else? [[This is where you insert a comment about the delicious irony, that P vs. NP itself<\/strong> is a perfect example of a monstrously-hard problem for which we could nevertheless recognize a solution if we saw one—and hence, part of the explanation for why it’s so hard to prove P\u2260NP is that P\u2260NP…]]<\/em><\/li>\n
- In the 1930s, G\u00f6del and Turing taught us that not only are certain mathematical statements undecidable<\/em> (within the standard axiom systems for set theory and even arithmetic), but there’s not even an algorithm to tell which statements have a proof or disproof and which don’t.\u00a0 Sure, you can try checking every possible proof, one by one—but if you haven’t yet found a proof, then there’s no general way to tell whether that’s because there is<\/em> no proof, or whether you simply haven’t searched far enough.\u00a0 On the other hand, if you restrict your attention to, say, proofs consisting of 1,000,000 symbols or less, then enumerating every proof does<\/em> become possible.\u00a0 However, it only becomes “possible” in an extremely Platonic sense: if there are 21,000,000<\/sup> proofs to check, then the sun will have gone cold and the universe degenerated into black holes and radiation long before your computer’s made a dent.\u00a0 So, the question arises of whether G\u00f6del and Turing’s discoveries have a “finitary” analogue: are there classes of mathematical statements that have short<\/em> proofs, but for which the proofs can’t be found in any reasonable amount of time?<\/li>\n<\/ul>\n
Basically, P vs. NP is the mathematical problem that you’re inevitably led to if you try to formalize any of the four questions above.<\/p>\n
Admittedly, in order to state<\/em> the problem formally, we need to make a choice: we interpret the phrase “fast algorithm” to mean “deterministic Turing machine that uses a number of steps bounded by a polynomial in the size of the input, and which always outputs the correct answer (yes, there is a solution satisfying the stated constraints, or no, there isn’t one).”\u00a0 There are other natural ways to interpret “fast algorithm” (probabilistic algorithms? quantum algorithms? linear time? linear time with a small constant? subexponential time? algorithms that only work on most<\/em> inputs?), and many are better depending on the application.\u00a0 A key point, however, is that whichever<\/em> choices we made, we’d get a problem that’s staggeringly hard, and for essentially the same reasons as P vs. NP is hard!\u00a0 And therefore, out of a combination of mathematical convenience and tradition, computer scientists like to take P vs. NP as our “flagship example” of a huge class<\/em> of questions about what is and isn’t feasible for computers, none<\/em> of which we know how to answer.<\/p>\n
So, those of you who just wandered into the tent: care to know more?\u00a0 The good news is that lots of excellent resources already exist. \u00a0 I suggest starting with the Wikipedia article on P vs. NP<\/a>, which is quite good.\u00a0 From there, you can move on to Avi Wigderson’s 2006 survey P, NP and mathematics – a computational complexity perspective<\/a>, or Mike Sipser’s The History and Status of the P vs. NP Question<\/a> (1992) for a more historical perspective (and a translation of a now-famous 1956 letter from G\u00f6del to von Neumann, which first asked what we’d recognize today as the P vs. NP question).<\/p>\n
After you’ve finished the above … well, the number of P vs. NP resources available to you increases exponentially with the length of the URL.\u00a0 For example, without even leaving the scottaaronson.com domain, you can find the following:<\/p>\n
\n
- Ten Reasons to Believe P\u2260NP<\/a><\/li>\n
- Great Ideas in Theoretical Computer Science Lecture 9<\/a> (P and NP)<\/li>\n
- Quantum Computing Since Democritus Lecture 6<\/a> (P, NP, and Friends)<\/li>\n
- Has There Been Progress on the P vs. NP Question?<\/a> (PowerPoint talk, from the Barriers workshop last year in Princeton)<\/li>\n
- Is P vs. NP Formally Independent?<\/a> (2003 survey article)<\/li>\n
- Algebrization: A New Barrier in Complexity Theory<\/a> (2009 paper by Avi Wigderson and myself)<\/li>\n<\/ul>\n
Feel free to use the comments section to suggest other resources, or to ask and answer basic questions about the P vs. NP problem, why it’s hard, why it’s important, how it relates to other problems, why Deolalikar’s attempt apparently failed, etc.\u00a0 Me, I think I’ll be taking a break from this stuff.<\/p>\n","protected":false},"excerpt":{"rendered":"
A reader named Darren commented on my last post: I have this feeling that this whole P and NP thing is not only a profound problem that needs solving, but something that can be infinitely curious to try and wrap your mind around\u2026 Thing is- there\u2019s a whole world of great minded, genius hackers out […]<\/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_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-459","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\/459","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=459"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/459\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=459"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=459"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=459"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}