Complexity Dojo

Main Zoo - Complexity Garden - Zoo Glossary - Zoo References - Chris' Complexity Dojo

---

Major Theorems: Cook-Levin - Savitch's - Ladner's - Blum Speedup - Impagliazzo-Widgerson - Toda's - Natural Proofs

Proof Techniques: Diagonalization

In complexity theory, it isn't enough to say that something is impossible; you have to prove it. So here in the Complexity Dojo, we introduce several major theorems and proof techniques that will go a long way.

Of course, there are going to be disagreements as to what a "major theorem" is, so this is all in the opinion of the Tour Guide and any other contributors. The main focus, though, will be on theorems that illustrate important concepts more than on theorems which have a direct impact. If you feel that the list of theorems is somehow terribly deficient for the lack of a specific theorem, please add it!

For those of you not used to mathematical proofs in general, here's some resources that may help:

• One of the various textbooks on the subject, such as that by Maddox.
• Mathematical Proof, a book on WikiBooks. (As of the time of this writing, it is woefully incomplete, but it should improve.)
• Wikipedia entry on Mathematical proof.
• MathWorld's definitions of Proof and Theorem. Also good is the page on proof by contradiction.

Of course, none of these resources can compare with taking a class that requires proofs (real analysis or complexity theory make good candidates), or a class directly about proofs.

Major Theorems

• Cook-Levin Theorem: SAT ∈ NP-complete.
• Savitch's Theorem: NSPACE(f(n)) ⊆ DSPACE(f²(n)), PSPACE = NPSPACE
• Ladner's Theorem P ≠ NP implies that NP-intermediate problems exist.
• Blum Speedup Theorem: Some problems do not have optimal solutions.
• Impagliazzo-Widgerson Theorem: P = BPP unless E has sub-exponential circuits.
• Toda's Theorem: PH ⊆ P^#P.
• Natural Proofs

Proof Techniques

• Diagonalization: Method of showing that an enumeration of a set is incomplete.