 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
 Peasant multiplication
 Division by two
 Exponentiating by squaring
 Addition chain
 Presburger arithmetic
Computability theory: models of computation
 Arithmetic circuits
 Algorithm
 Finite state automaton
 Mealy machine
 Minsky register machine
 Moore machine
 State diagram
 State transition system
 Deterministic finite state machine
 Nondeterministic finite state machine
 Generalized nondeterministic finite state machine
 Regular language
 Pumping lemma
 MyhillNerode theorem
 Regular expression
 Regular grammar
 Prefix grammar
 Tree automaton
 Pushdown automaton
 Büchi automaton
 Chomsky hierarchy
 Register machine
 Stack machine
 Petri net
 Post machine
 Rewriting
 Markov algorithm
 Term rewriting
 String rewriting system
 Lsystem
 KnuthBendix completion algorithm
 Star height
 Cellular automaton
 Rule 110 cellular automaton
 Conway's Game of Life
 Langton's ant
 Edge of chaos
 Turing machine
 Deterministic Turing machine
 Nondeterministic Turing machine
 Alternating automaton
 Alternating Turing machine
 Turingcomplete
 Turing tarpit
 Oracle machine
 Lambda calculus
 Combinatory logic
 Combinator
 Parallel computing
 Flynn's taxonomy
 Quantum computer
 ChurchTuring thesis
Decision problems
 Entscheidungsproblem
 Halting problem
 Post correspondence problem
 Decidable language
 Undecidable language
 Word problem for groups
 Wang tile
 Penrose tiling
Definability questions
 Computable number
 Definable number
 Halting probability
 Algorithmic information theory
 Algorithmic probability
 Data compression
Complexity theory
 Advice (complexity)
 Amortized analysis
 Arthur–Merlin protocol
 Best and worst cases
 Busy beaver
 Circuit complexity
 Constructible function
 Cook's theorem
 Exponential time
 Function problem
 Linear time
 Linear speedup theorem
 Natural proof
 Polynomial time
 Polynomialtime manyone reduction
 Polynomialtime Turing reduction
 Savitch's theorem
 Space hierarchy theorem
 Speed Prior
 Speedup theorem
 Subquadratic time
 Time hierarchy theorem
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
 Nondeterminism
 Nondeterministic Turing machine
 Interactive computation
 Interactive proof system
 Probabilistic Turing Machine
 Approximation algorithm
 Simulated annealing
 Ant colony algorithm
 Game semantics
 Generalized game
 Multipleagent system
 Parameterized complexity
 Process calculi
 Hypercomputation
 Real computation
Categories: Complexity classes
 Mathematicsrelated lists
 Computability theory
 Theory of computation
Wikimedia Foundation. 2010.