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.

Table of contents

1 Calculation 2 Computability theory: models of computation 3 Decision problems 4 Definability questions 5 Complexity theory 6 Complexity classes 7 Named problems 8 Extensions

Calculation

• Mathematical expression
  • Expression, evaluation
  • Bracket
  • S-expression, M-expression
  • Four fours
• Calculator
  • Abacus
  • Napier's bones
  • Slide rule
  • Generating trigonometric tables
• Order of operations, infix notation, reverse Polish Notation
• Multiplication algorithm
  • Peasant multiplication
• Division by two
• Exponentiating by squaring
• Presburger arithmetic

Computability theory: models of computation

• Algorithm
  • Procedure, recursion
• Finite state automaton
  • Mealy machine
  • Minsky machine
  • Moore machine
  • Regular language
    • Pumping lemma
    • Myhill-Nerode theorem
  • Regular expression
  • Regular grammar
  • Tree automaton
• Pushdown automaton
  • Context-free grammar
• Büchi automaton
• Chomsky hierarchy
  • Context-sensitive language
  • Recursively enumerable language
• Petri net
• Post machine
• Markov algorithm
  • String rewriting system
  • L-system
• Cellular automaton
  • Conway's Game of Life
• Turing machine
  • Turing-complete
  • Turing tarpit
  • Oracle machine
• Lambda calculus
• Combinatory logic
  • Combinator
• Parallel computing
• Flynn's taxonomy
• Quantum computer
• Church-Turing thesis
  • Recursive function

Decision problems

• Entscheidungsproblem
• Halting problem
  • Correctness
• Post correspondence problem
• Decidable language
  • Undecidable language
• Word problem for groups
• Wang tile

Definability questions

• Computable number
• Definable number
• Halting probability
• Algorithmic information theory
• Data compression

Complexity theory

• Polynomial time
• Exponential time
• Time hierarchy theorem
• Polynomial-time many-one reduction
• Polynomial-time Turing reduction

Complexity classes

• Complexity classes P and NP
• P-complete
  • NP, NP-complete, NP-hard, NP-equivalent
  • Co-NP, Co-NP-complete
• Sharp-P, Sharp-P-complete
• PSPACE, PSPACE-complete
• EXPSPACE, EXPTIME, EXPTIME-complete
• BPP
• BQP
• Class NC
• RP
• UP (complexity)
• ZPP

Named problems

• Clique problem
• Hamiltonian cycle problem
• Integer factorization
• Knapsack problem
• Satisfiability problem
  • 3-satisfiability
• Subset sum problem
• Traveling salesman problem

Extensions

• Probabilistic algorithm
• Non-deterministic Turing machine
• Probabilistic Turing Machine
• Hypercomputation