{"id":392,"date":"2009-05-19T20:23:02","date_gmt":"2009-05-20T00:23:02","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=392"},"modified":"2009-05-19T20:23:02","modified_gmt":"2009-05-20T00:23:02","slug":"sidesplitting-proofs","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=392","title":{"rendered":"Sidesplitting proofs"},"content":{"rendered":"

One thing I’ve always liked about theoretical computer science is the number of proofs that are patently ridiculous—whose concluding steps seem to call more for a gong or cymbal than a “QED” box.\u00a0 This is a property that CS theory inherited from logic, and that it shares with several other mathematical fields (though by no means all of them).\u00a0 The titans of the comedy-proof genre are of course G\u00f6del and Turing’s undecidability results, the latter of which arguably found its best expression as a poem<\/a>.\u00a0 But there are other examples all over the place, and many aren’t as well known as they should be.<\/p>\n

I was reminded of this side of theory when my student Andy Drucker and I came up with yet another absurd proof: basically, a theorem that’s true for one reason if a certain algebraic problem is hard, and true for a completely different reason if the problem is easy.\u00a0 We’re still writing it up, so at Andy’s request I won’t spill the joke yet.\u00a0 For now, please content yourself with the following tried-and-true komedy klassics.<\/p>\n

Theorem 1 (folklore):<\/em> E<\/strong> (that is, the class of problems solvable in 2O(n)<\/sup> time) does not equal PSPACE<\/strong>, the class of problems solvable in polynomial space.\u00a0 (Though we have no idea how to prove which one is bigger than the other one—or that they’re incomparable, as seems most likely.)<\/p>\n

Proof:<\/em> Suppose E<\/strong>=PSPACE<\/strong>.\u00a0 Then E<\/strong>=EXP<\/strong> by padding, where EXP<\/strong> is the class of problems solvable in 2poly(n)<\/sup> time.\u00a0 But that would contradict the Time Hierarchy Theorem.<\/p>\n

Theorem 2 (classic, attributed to Levin):<\/em> One can give a fixed, explicit algorithm, which finds satisfying assignments to Boolean formulas in polynomial time whenever they exist, assuming P<\/strong>=NP<\/strong>.<\/p>\n

Proof:<\/em> let M1<\/sub>, M2<\/sub>, … be a list of Turing machines that take a SAT instance \u03c6 as input.\u00a0 The algorithm is as follows: dovetail (that is, run a step of M1<\/sub>, then another step of M1<\/sub> and a step of M2<\/sub>, then another step of M1<\/sub> and M2<\/sub> and a step of M3<\/sub>, etc.), halting when one of the machines has output a valid satisfying assignment for \u03c6.\u00a0 If P<\/strong>=NP<\/strong>, then there’s some Turing machine Mi<\/sub> in the list that solves SAT, and that causes the whole algorithm to work in polynomial time assuming \u03c6 was satisfiable.\u00a0 (The fact that you’re also simulating quadrillions of other machines merely slows things down by a “polynomial factor,” independent of the input size n.)<\/p>\n

Theorem 3 (Gutfreund, Shaltiel, Ta-Shma<\/a>):<\/em> Let A be an algorithm that’s supposed to solve SAT in polynomial time (that is, find a satisfying assignment whenever one exists), but that actually fails on some SAT instance of size n.\u00a0 Then if someone gives you the source code of A, you can, in time polynomial in n, find a specific SAT instance that actually witnesses A’s failure.<\/p>\n

Proof:<\/em> By the Cook-Levin Theorem, you can create a SAT instance\u00a0\u03c6(x) which encodes the statement, “x is a SAT instance of size n on which A fails (that is, either there’s a satisfying assignment A fails to find, or A outputs an assignment for x that isn’t satisfying).”\u00a0 Then feed \u03c6 as input to A.\u00a0 There are two cases: on the one hand, if A succeeds, then it’s helpfully provided you with a SAT instance on which it itself fails.\u00a0 On the other hand, if A fails on \u03c6, then \u03c6 itself is the SAT instance you were looking for.<\/p>\n

Theorem 4 (Barak et al.<\/a>):<\/em> There exist programs that can’t be obfuscated—that is, for which having the actual code of the program lets you do something that you couldn’t do if you could only run the program as a subroutine.<\/p>\n

Proof:<\/em> Let P be a program that takes a string x as input, and does the following.\u00a0 First, if x=a, where a is some n-bit “secret string” hardwired into P’s source code, then P(a) outputs another n-bit secret string b.\u00a0 Second, if x is the source code of a program Q such that Q(a) outputs b (after some fixed number of steps, say t=O(n)), then P outputs a third secret string c.\u00a0 Third, if x satisfies neither constraint, then P(x) outputs “FAIL.”\u00a0 Now, given the source code of P, it’s easy to find c: just run P with its own code as input.\u00a0 On the other hand, if you can only run P as a subroutine, then (unless you get extremely lucky) it will take exponential time to find any x for which P(x) outputs anything besides “FAIL.”\u00a0 Hence it’s infeasible to find c by running P, and yet there’s no way to obfuscate P’s source code so as to hide c.<\/p>\n

Theorem 5 (attributed by Razborov and Rudich<\/a> to Wigderson):<\/em> No natural proof can prove better than a half-exponential lower bound on the circuit complexity of the discrete logarithm problem.\u00a0 (Here half-exponential<\/em> refers to a function f—which exists, but can’t be described analytically—such that f(f(n)) grows exponentially with n.)<\/p>\n

Proof Sketch:<\/em> Suppose we can prove an f(n) lower bound on the circuit complexity of discrete log, using a natural proof.\u00a0 Then by the definition of natural proof, there exists a 2O(n)<\/sup>-time algorithm to distinguish a truly random function g:{0,1}n<\/sup>\u2192{0,1} from a function with circuit size f(n).\u00a0 This means that any efficiently-computable pseudorandom function family (PRFF), with seed length m=f(n), can be distinguished from a random function in exp(f-1<\/sup>(m)) time.\u00a0 By standard equivalence theorems in cryptography, this means that any purported one-way function—so for example, the modular exponentiation function—can be inverted in exp(f-1<\/sup>(n)) time.\u00a0 In other words, to prove a natural f(n) lower bound for the discrete logarithm problem, you must also discover an exp(f-1<\/sup>(n))-time algorithm for the discrete logarithm problem.<\/em>\u00a0 As you show the discrete log problem to be harder, you simultaneously show it to be easier!\u00a0 And when f is greater than half-exponential, the lower bound becomes greater than the upper bound.<\/p>\n

What is it that makes these theorems funny?\u00a0 (Alright, maybe not ha-ha funny, but at least snort-snort funny?)\u00a0 This is one case where a few readers might want me to break the rule about never explaining a joke.\u00a0 Theorems 1 and 2 are sort of like “you’re lost,” as an answer to the balloonist’s plea of “where am I?”: they’re logically impeccable yet tell you nothing whatsoever about what you wanted to know.\u00a0 Theorems 3 and 4 are like someone who’s so hungry he devours the menu at a restaurant, not even realizing that the menu itself was listed<\/em> on the menu.\u00a0 They seem to involve a category mistake: a reference gluttonously repurposed as a referent only to become a reference again.\u00a0 (This, of course, is the joke behind G\u00f6del’s theorem as well.)\u00a0 Theorem 5 is like a literary critic proving there’s no ‘reality’ separate from race, class, and gender biases, using arguments that are so well-grounded, even a white male plutocrat would have to concede their truth.\u00a0 The case is a self-immolating one: every argument that makes it stronger necessarily makes it weaker as well.<\/p>\n

So what’s your<\/em> favorite sidesplitting proof?<\/p>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

One thing I’ve always liked about theoretical computer science is the number of proofs that are patently ridiculous—whose concluding steps seem to call more for a gong or cymbal than a “QED” box.\u00a0 This is a property that CS theory inherited from logic, and that it shares with several other mathematical fields (though by no […]<\/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_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,30],"tags":[],"class_list":["post-392","post","type-post","status-publish","format-standard","hentry","category-complexity","category-mirrored-on-csail-blog"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/392","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=392"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/392\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=392"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=392"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=392"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}