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.
| Contents |
Calculation
- Mathematical expression
- Lookup table, mathematical table, multiplication table
- Calculator
- Counting rods
- Abacus, Chinese abacus, Roman abacus
- Torquetum
- Napier's bones, rabdology
- Pascal's calculator
- Slide rule
- Generating trigonometric tables
- Difference engine
- Analytical engine
- Ada Byron's notes on the analytical engine
- Adding machine
- Mechanical calculator
- Comptometer
- Differential analyser
- Curta calculator
- History of computers
- Order of operations, infix notation, reverse Polish notation
- Multiplication algorithm
- Division by two
- Exponentiating by squaring
- Addition chain
- Presburger arithmetic
Computability theory: models of computation
- 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
- Entscheidungsproblem
- Halting problem
- Post correspondence problem
- Decidable language
- Word problem for groups
- Wang tile
- Penrose tiling
Definability questions
- Computable number
- Definable number
- Halting probability
- Algorithmic information theory
- Algorithmic probability
- Data compression
- Reductibility
Complexity theory
- Best and worst cases
- Linear time
- Polynomial time
- Subquadratic time
- Exponential time
- Time hierarchy theorem
- Space hierarchy theorem
- Polynomial-time many-one reduction
- Polynomial-time Turing reduction
- Cook's theorem
- constructible function
- Busy beaver
- Speed Prior
- Speedup theorem
- Linear speedup theorem
- Savitch's theorem
- Natural proof
- Advice (complexity)
- Arthur-Merlin protocol
- Amortized analysis
- Function problem
Complexity classes
See the list of complexity classes
Named problems
- Clique problem
- Hamiltonian cycle problem
- Hamiltonian path problem
- Integer factorization
- Knapsack problem
- Satisfiability problem
- Subset sum problem
- 3SUM
- Traveling salesman problem
- Vertex cover problem
- One way function
- Set cover problem
- Independent set problem
Extensions
- Probabilistic algorithm, randomized algorithm
- Las Vegas algorithm
- Non-determinism
- Non-deterministic Turing machine
- Interactive computation
- Interactive proof system
- Probabilistic Turing Machine
- Approximation algorithm
- Fixed-parameter algorithm
- Simulated annealing
- Ant colony algorithm
- Game semantics
- Generalized game
- Multiple agent system
- Process calculus
- Hypercomputation
- Real computation