Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard computations are, in quantitative terms, both with upper bounds (algorithms whose complexity in the worst cases, as use of computing resources, can be estimated), and from below (proofs that no procedure to carry out some task can be very fast).
For more abstract foundational matters, see the list of mathematical logic topics.
| Table of contents |
|
2 Computability theory: models of computation 3 Decision problems 4 Definability questions 5 Complexity theory 6 Complexity classes 7 Named problems 8 Extensions |
Calculation
Computability theory: models of computation
Decision problems
Definability questions
Complexity theory
Complexity classes
Named problems
Extensions