{"id":240,"date":"2007-05-20T10:59:22","date_gmt":"2007-05-20T18:59:22","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=240"},"modified":"2007-05-20T10:59:22","modified_gmt":"2007-05-20T18:59:22","slug":"a-woitian-links-links-links-post-slightly-stale-but-still-edible","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=240","title":{"rendered":"A Woitian links, links, links post (slightly stale but still edible)"},"content":{"rendered":"<p>Razborov and Rudich <a href=\"http:\/\/www.eatcs.org\/activities\/awards\/goedel.html\">won the G\u00f6del Prize<\/a> for <a href=\"http:\/\/www.cs.cmu.edu\/~rudich\/papers\/natural.ps\">&#8220;Natural Proofs&#8221;<\/a>, which probably did as much as any single paper to elucidate the nature of the P vs. NP problem.  (More from the <a href=\"http:\/\/weblog.fortnow.com\/2007\/05\/godel-prize-natural-proofs-my-2-cents.html#comments\">Bearded One<\/a> and the <a href=\"http:\/\/dabacon.org\/pontiff\/?p=1518\">Pontiff<\/a>.) Loosely speaking, R&#038;R showed that any circuit lower bound satisfying certain extremely broad criteria would &#8220;bite its own tail,&#8221; and lead to efficient algorithms to distinguish random from pseudorandom functions &#8212; the very sort of thing that we wanted to prove was hard. This doesn&#8217;t by any means imply that a P\u2260NP proof is impossible, but it does show how the problem has a strange, self-referential character that&#8217;s not quite like anything previously encountered in mathematics, including in the work of G\u00f6del and Turing.  Technically simple but conceptually profound, the paper is also a masterpiece of clear, forceful exposition.  When I first came across it as an undergrad at Cornell, I knew complexity was my subject.<\/p>\n<p>Following on the heels of the <em>New Yorker<\/em>, the <em>New York Times<\/em> <a href=\"http:\/\/www.nytimes.com\/2007\/05\/15\/science\/15cern.html\">ran its own epic<\/a> on the Large Hadron Collider.  So science writers <em>can<\/em> do a decent job when they feel like it.  Why can&#8217;t they write about P vs. NP the same way?  Oh, right &#8230; them big machines &#8230;<\/p>\n<p>Andy Drucker <a href=\"http:\/\/andysresearch.blogspot.com\/2007\/05\/feed-me.html\">poses the following problem<\/a>: suppose there are n blog posts, and for each post b<sub>i<\/sub>, you&#8217;re told only that it was posted during the time interval [t<sub>i<\/sub>,u<sub>i<\/sub>].  Is there an efficient algorithm to count how many orderings of the blog posts are compatible with that information?  Alternatively, is the problem #P-complete?  Let me stress that Andy doesn&#8217;t know the answer to this question, and neither do I.<\/p>\n<p>A certain MIT undergrad of my acquaintance sent the following letter to MIT&#8217;s <a href=\"http:\/\/en.wikipedia.org\/wiki\/DMCA\">DMCA<\/a> enforcement office.<\/p>\n<blockquote><p>Dear MIT DMCA Agent,<\/p><\/blockquote>\n<blockquote><p>After viewing <em>Scoop<\/em> and receiving your notice, I was more than happy to comply with NBC&#8217;s request to destroy it. Rest assured that I will no longer be downloading or sharing any post-Manhattan Woody Allen films.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Razborov and Rudich won the G\u00f6del Prize for &#8220;Natural Proofs&#8221;, which probably did as much as any single paper to elucidate the nature of the P vs. NP problem. (More from the Bearded One and the Pontiff.) Loosely speaking, R&#038;R showed that any circuit lower bound satisfying certain extremely broad criteria would &#8220;bite its own [&hellip;]<\/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,11,3],"tags":[],"class_list":["post-240","post","type-post","status-publish","format-standard","hentry","category-complexity","category-nerd-interest","category-procrastination"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/240","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=240"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/240\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=240"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=240"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=240"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}