{"id":676,"date":"2011-06-07T18:51:45","date_gmt":"2011-06-07T23:51:45","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=676"},"modified":"2017-01-12T16:40:45","modified_gmt":"2017-01-12T21:40:45","slug":"tools-for-the-modern-complexity-theorist","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=676","title":{"rendered":"Tools for the modern complexity theorist"},"content":{"rendered":"

You’re deep in the Congo.\u00a0 You’ve got an iPhone with some charge left, but there’s no cell tower for hundreds of miles.\u00a0 With life-or-death urgency, you need to know the definition of the complexity class SBP<\/a> and its relationship to BPPpath<\/sub><\/a>.\u00a0 What do you do?<\/p>\n

Not to worry: Satoshi Hada has created a free Complexity Zoo app<\/a> for the iPad and iPhone.\u00a0 I tried it out and it works great!<\/p>\n

\n

You get a cold call from yet another solitary genius who’s discovered a simple linear-time 3SAT algorithm.\u00a0 You tell him to implement the algorithm and test it out, and then<\/em> you’ll talk.\u00a0 Half an hour later, he tells you he’s done so and it works perfectly.\u00a0 So you tell him to go factor the 617-digit RSA challenge number<\/a>.\u00a0 But being an iconoclastic genius, he never learned how to reduce factoring to 3SAT.\u00a0 What do you do?<\/p>\n

Relax: answering challenge #2 from this blog post<\/a> even before the post went up, USC students Henry Yuen and Joe Bebel have created a great web application called ToughSAT<\/a>, which generates hard SAT instances on demand, based on factoring, subset sum, or even a “hard problem cocktail.”\u00a0 As a commenter helpfully alerted us, a few years ago Paul Purdom and Amr Sabry of Indiana University already created a similar site<\/a> that generates hard SAT instances based on factoring.<\/p>\n","protected":false},"excerpt":{"rendered":"

You’re deep in the Congo.\u00a0 You’ve got an iPhone with some charge left, but there’s no cell tower for hundreds of miles.\u00a0 With life-or-death urgency, you need to know the definition of the complexity class SBP and its relationship to BPPpath.\u00a0 What do you do? Not to worry: Satoshi Hada has created a free Complexity […]<\/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_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_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-676","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\/676","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=676"}],"version-history":[{"count":6,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/676\/revisions"}],"predecessor-version":[{"id":3129,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/676\/revisions\/3129"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=676"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=676"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=676"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}