List of computability and complexity topics
This article will address the topic of List of computability and complexity topics, which has aroused growing interest in recent times. From different perspectives and approaches, this topic has generated debates and reflections in various areas, such as society, culture, politics, economics and science. Its implications, its evolution over time and its relevance today will be explored, with the aim of offering a comprehensive and detailed vision of List of computability and complexity topics. Its different dimensions will be examined, analyzing its consequences, its influence on the global level and its future projection. Through a deep and exhaustive analysis, the aim is to contribute to the understanding and knowledge of List of computability and complexity topics, thus enriching the debate and reflection around this topic of undoubted importance.
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.
- Lookup table
- History of computers
- Multiplication algorithm
- Division by two
- Exponentiating by squaring
- Addition chain
- Presburger arithmetic
Computability theory: models of computation
- 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
- 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
- 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
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
- Simulated annealing
- Ant colony optimization algorithms
- Game semantics
- Generalized game
- Multiple-agent system
- Parameterized complexity
- Process calculi
- Hypercomputation
- Real computation
- Computable analysis