Complexity Dojo

From Complexity Zoo
Jump to: navigation, search

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:

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

Proof Techniques

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