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).
- Comment
- enThis 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).
- Has abstract
- enThis 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.
- Hypernym
- List
- Is primary topic of
- List of computability and complexity topics
- Label
- enList of computability and complexity topics
- Link from a Wikipage to another Wikipage
- 2-satisfiability
- 3SUM
- Addition chain
- Advice (complexity)
- Algorithm
- Algorithmic information theory
- Algorithmic probability
- Alternating automaton
- Alternating Turing machine
- Amortized analysis
- Ant colony algorithm
- Approximation algorithm
- Arithmetic circuit complexity
- Arthur–Merlin protocol
- B, C, K, W System
- Best and worst cases
- Boolean satisfiability problem
- Büchi automaton
- Busy beaver
- Calculation
- Category:Complexity classes
- Category:Mathematics-related lists
- Category:Outlines of mathematics and logic
- Category:Theory of computation
- Category:Wikipedia outlines
- Cellular automaton
- Chomsky hierarchy
- Church-Turing thesis
- Circuit complexity
- Clique problem
- Combinator
- Combinatory logic
- Computability theory
- Computable analysis
- Computable number
- Computation
- Computational complexity theory
- Constructible function
- Context-free grammar
- Context-sensitive grammar
- Context-sensitive language
- Conway's Game of Life
- Cook's theorem
- Correctness (computer science)
- Data compression
- Decidable language
- Decision problem
- Definable number
- Deterministic finite automaton
- Deterministic Turing machine
- Division by two
- Edge of chaos
- Entscheidungsproblem
- Exponential hierarchy
- Exponential time
- Exponentiating by squaring
- Finite state automaton
- Flynn's taxonomy
- Function problem
- Game semantics
- Generalized game
- Generalized nondeterministic finite automaton
- Generalized star height problem
- Generating trigonometric tables
- Halting probability
- Halting problem
- Hamiltonian cycle problem
- Hamiltonian path problem
- History of computers
- Hypercomputation
- Independent set problem
- Integer factorization
- Interactive computation
- Interactive proof system
- Knapsack problem
- Knuth–Bendix completion algorithm
- Lambda calculus
- Langton's ant
- Las Vegas algorithm
- Linear speedup theorem
- Linear time
- List of algorithm general topics
- List of algorithms
- List of complexity classes
- List of mathematical logic topics
- Lookup table
- L-system
- Markov algorithm
- Mathematical table
- Mealy machine
- Minsky register machine
- Moore machine
- Multiple-agent system
- Multiplication algorithm
- Multiplication table
- Myhill-Nerode theorem
- Natural proof
- Non-determinism (disambiguation)
- Nondeterministic finite automaton
- Non-deterministic Turing machine
- One way function
- Oracle machine
- Parallel computing
- Parameterized complexity
- Peasant multiplication
- Penrose tiling
- Petri net
- Pi-calculus
- Polynomial hierarchy
- Polynomial time
- Polynomial-time many-one reduction
- Polynomial-time Turing reduction
- Post correspondence problem
- Post–Turing machine
- Prefix grammar
- Presburger arithmetic
- Probabilistic algorithm
- Probabilistic Turing Machine
- Process calculi
- Pumping lemma
- Pushdown automaton
- Quantum computer
- Randomized algorithm
- Real computation
- Recursion
- Recursion (computer science)
- Recursively enumerable language
- Register machine
- Regular expression
- Regular grammar
- Regular language
- Rewriting
- Rule 110 cellular automaton
- Satisfiability problem
- Savitch's theorem
- Scholz conjecture
- Set cover problem
- Simulated annealing
- Space hierarchy theorem
- Speed Prior
- Stack machine
- Star height
- Star height problem
- State diagram
- State transition system
- String rewriting system
- Subquadratic time
- Subroutine
- Subset sum problem
- Term rewriting
- Time hierarchy theorem
- Traveling salesman problem
- Tree automaton
- Turing-complete
- Turing machine
- Turing tarpit
- Undecidable language
- Universal quantum computer
- Vertex cover problem
- Wang tile
- Weihrauch reducibility
- Word problem for groups
- SameAs
- 4qPLr
- Q6613099
- Subject
- Category:Complexity classes
- Category:Mathematics-related lists
- Category:Outlines of mathematics and logic
- Category:Theory of computation
- Category:Wikipedia outlines
- WasDerivedFrom
- List of computability and complexity topics?oldid=1095686803&ns=0
- WikiPageLength
- 5209
- Wikipage page ID
- 353748
- Wikipage revision ID
- 1095686803
- WikiPageUsesTemplate
- Template:Short description