### Sidesplitting proofs

Tuesday, May 19th, 2009One 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. 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). The titans of the comedy-proof genre are of course Gödel and Turing’s undecidability results, the latter of which arguably found its best expression as a poem. But there are other examples all over the place, and many aren’t as well known as they should be.

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. We’re still writing it up, so at Andy’s request I won’t spill the joke yet. For now, please content yourself with the following tried-and-true komedy klassics.

*Theorem 1 (folklore):* **E** (that is, the class of problems solvable in 2^{O(n)} time) does not equal **PSPACE**, the class of problems solvable in polynomial space. (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.)

*Proof:* Suppose **E**=**PSPACE**. Then **E**=**EXP** by padding, where **EXP** is the class of problems solvable in 2^{poly(n)} time. But that would contradict the Time Hierarchy Theorem.

*Theorem 2 (classic, attributed to Levin):* One can give a fixed, explicit algorithm, which finds satisfying assignments to Boolean formulas in polynomial time whenever they exist, assuming **P**=**NP**.

*Proof:* let M_{1}, M_{2}, … be a list of Turing machines that take a SAT instance φ as input. The algorithm is as follows: dovetail (that is, run a step of M_{1}, then another step of M_{1} and a step of M_{2}, then another step of M_{1} and M_{2} and a step of M_{3}, etc.), halting when one of the machines has output a valid satisfying assignment for φ. If **P**=**NP**, then there’s some Turing machine M_{i} in the list that solves SAT, and that causes the whole algorithm to work in polynomial time assuming φ was satisfiable. (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.)

*Theorem 3 (Gutfreund, Shaltiel, Ta-Shma):* 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. 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.

*Proof:* By the Cook-Levin Theorem, you can create a SAT instance φ(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).” Then feed φ as input to A. 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. On the other hand, if A fails on φ, then φ itself is the SAT instance you were looking for.

*Theorem 4 (Barak et al.):* 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.

*Proof:* Let P be a program that takes a string x as input, and does the following. 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. 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. Third, if x satisfies neither constraint, then P(x) outputs “FAIL.” Now, given the source code of P, it’s easy to find c: just run P with its own code as input. 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.” 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.

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

*Proof Sketch:* Suppose we can prove an f(n) lower bound on the circuit complexity of discrete log, using a natural proof. Then by the definition of natural proof, there exists a 2^{O(n)}-time algorithm to distinguish a truly random function g:{0,1}^{n}→{0,1} from a function with circuit size f(n). 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}(m)) time. 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}(n)) time. In other words, *to prove a natural f(n) lower bound for the discrete logarithm problem, you must also discover an exp(f ^{-1}(n))-time algorithm for the discrete logarithm problem.* As you show the discrete log problem to be harder, you simultaneously show it to be easier! And when f is greater than half-exponential, the lower bound becomes greater than the upper bound.

What is it that makes these theorems funny? (Alright, maybe not ha-ha funny, but at least snort-snort funny?) This is one case where a few readers might want me to break the rule about never explaining a joke. 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. 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* on the menu. They seem to involve a category mistake: a reference gluttonously repurposed as a referent only to become a reference again. (This, of course, is the joke behind Gödel’s theorem as well.) 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. The case is a self-immolating one: every argument that makes it stronger necessarily makes it weaker as well.

So what’s *your* favorite sidesplitting proof?