[Computational Complexity] Complexity versus Computability
To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. Computability (Recursion) Theory started in the 1930's with the work of Turing, Church, Gödel and Kleene and complexity theory gathered steam in the 60's. Complexity theory derives many of its definitions from computability theory such as Turing machines, reducibility, completeness and lowness and the polynomial-time hierarchy is an analogue of the arithmetic hierarchy. Several complexity theorists originally received their Ph.D. in computability theory.
One can say computational complexity is just computability theory with resource bounds but the fields feel quite different.
- Complexity theorists consider themselves part of the theoretical computer science community and find themselves mostly in CS departments. Recursion theorists consider themselves logicians and find themselves mostly in math departments.
- Complexity theorists try to understand efficient computation analogous to theoretical physicists trying to understand how the universe works, where computability theorists consider more ethereal questions of logical definability. Consider the example of quantum computing: Many complexity theorists analyze the computational power of these machines where quantum has had virtually no effect on computability theory.
- Outside of diagonalization, the tools and techniques used in the fields are completely different. Rare does one see a priority or finite injury argument in complexity, whereas algebra and combinatorics don't appear in most computability proofs.
The difference in thinking hit me during a logic seminar where the speaker asked "How do we usually show that a language is computable?" I thought find an algorithm. The speaker answered his own question "Show that the language is c.e. and co-c.e."
Posted by Lance to Computational Complexity at 7/22/2005 09:13:00 AM