What is the difference between complexity theory and computability theory? Is there any overlap between the two or are they completely different? Or is one a subset of the other?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Put succinctly, computability theory is concerned with what can be computed versus what cannot; complexity is concerned with the resources required to compute the things that are computable.
As such, the fields are somewhat disjoint. Complexity theory is interested in a fine-grained classification of computable problems, with "it's uncomputable" as a worst-case scenario where we throw up our hands and give up. Computability theory (though one wouldn't realise this from an undergrad course) is interested in a fine-grained classification of uncomputable problems, with "it's computable" as the case at the bottom that's left to others to deal with.
However, there is some overlap of techniques, at least at a high level. In both cases, one typically uses the existence of an algorithm to demonstrate membership in a class and proofs of hardness are usually by reductions. Diagonalization also plays a role in both, proving things like the time and space hierarchy theorems in complexity, and the undecidability of halting problems in computability.
answered Sep 21, 2015 at 8:26
$\begingroup$
$\endgroup$
Computability is about what can be computed.
Complexity is about how efficiently can it be computed.
answered Sep 21, 2015 at 7:57