List of computability and complexity topics |
This is a list of computability and complexity topics, by Wikipedia page.
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. See also list of algorithms, list of algorithm general topics.
Computability theory: models of computation
Definability questions
Complexity classes
See the list of complexity
classes
- Exponential hierarchy
- Polynomial hierarchy
Named problems
Extensions
|