List of computability and complexity topics
(Redirected from Outline of computability and complexity)
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).
Calculation
[edit]Computability theory: models of computation
[edit]- Arithmetic circuits
- Algorithm
- Finite-state automaton
- Pushdown automaton
- Büchi automaton
- Chomsky hierarchy
- Register machine
- Stack machine
- Petri net
- Post machine
- Rewriting
- Star height
- Cellular automaton
- Turing machine
- Lambda calculus
- Combinatory logic
- Parallel computing
- Flynn's taxonomy
- Quantum computer
- Church–Turing thesis
Decision problems
[edit]Definability questions
[edit]Complexity theory
[edit]- Advice (complexity)
- Amortized analysis
- Arthur–Merlin protocol
- Best and worst cases
- Busy beaver
- Circuit complexity
- Constructible function
- Cook-Levin theorem
- Exponential time
- Function problem
- Linear time
- Linear speedup theorem
- Natural proof
- Polynomial time
- Polynomial-time many-one reduction
- Polynomial-time Turing reduction
- Savitch's theorem
- Space hierarchy theorem
- Speed Prior
- Speedup theorem
- Subquadratic time
- Time hierarchy theorem
Complexity classes
[edit]Named problems
[edit]Extensions
[edit]- Probabilistic algorithm, randomized algorithm
- Las Vegas algorithm
- Non-determinism
- Non-deterministic Turing machine
- Interactive computation
- Interactive proof system
- Probabilistic Turing Machine
- Approximation algorithm
- Simulated annealing
- Ant colony optimization algorithms
- Game semantics
- Generalized game
- Multiple-agent system
- Parameterized complexity
- Process calculi
- Hypercomputation
- Real computation
- Computable analysis
See also
[edit]- List of algorithm general topics
- List of mathematical logic topics – for more abstract foundational matters