{"id":4830,"date":"2020-06-01T14:00:33","date_gmt":"2020-06-01T19:00:33","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=4830"},"modified":"2020-10-13T18:43:48","modified_gmt":"2020-10-13T23:43:48","slug":"the-us-might-die-but-p-and-pspace-are-forever","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=4830","title":{"rendered":"The US might die, but P and PSPACE are forever"},"content":{"rendered":"\n

Today, I interrupt the news of the rapid disintegration of the United States of America, on every possible front at once (medical, economic, social…), to bring you something far more important: a long-planned two-hour podcast<\/a>, where theoretical physicist and longtime friend-of-the-blog Sean Carroll<\/a> interviews yours truly about complexity theory! Here’s Sean’s description of this historic event:<\/p>\n\n\n\n

There are some problems for which it\u2019s very hard to find the answer, but very easy to check the answer if someone gives it to you. At least, we think there are such problems; whether or not they really exist is the famous P vs NP problem<\/a>, and actually proving it will win you a million dollars<\/a>. This kind of question falls under the rubric of \u201ccomputational complexity theory,\u201d which formalizes how hard it is to computationally attack a well-posed problem. Scott Aaronson is one of the world\u2019s leading thinkers in computational complexity, especially the wrinkles that enter once we consider quantum computers as well as classical ones. We talk about how we quantify complexity, and how that relates to ideas as disparate as creativity, knowledge vs. proof, and what all this has to do with black holes and quantum gravity.<\/p><\/blockquote>\n\n\n\n

So, OK, I guess I should also comment on the national disintegration thing. As someone who was once himself the victim of a crazy police overreaction (albeit, trivial compared to what African-Americans regularly deal with), I was moved by the scenes of police chiefs in several American towns taking off their helmets and joining protesters to cheers. Not only is that a deeply moral thing to do, but it serves a practical purpose of quickly defusing the protests. Right now, of course, is an even worse time than usual<\/em> for chaos in the streets, with a lethal virus still spreading that doesn’t care whether people are congregating for good or for ill. If rational discussion of policy still matters, I support the current push to end the “qualified immunity” doctrine, end the provision of military training and equipment to police, and generally spur the nation’s police to rein in their psychopath minority.<\/p>\n","protected":false},"excerpt":{"rendered":"

Today, I interrupt the news of the rapid disintegration of the United States of America, on every possible front at once (medical, economic, social…), to bring you something far more important: a long-planned two-hour podcast, where theoretical physicist and longtime friend-of-the-blog Sean Carroll interviews yours truly about complexity theory! Here’s Sean’s description of this historic […]<\/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_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":[31,5,4,8],"tags":[],"class_list":["post-4830","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-quantum","category-the-fate-of-humanity"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4830","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=4830"}],"version-history":[{"count":2,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4830\/revisions"}],"predecessor-version":[{"id":5011,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4830\/revisions\/5011"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4830"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4830"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4830"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}