List Of Computability And Complexity Topics

Calculation

• Mathematical expression
• Expression, expression (mathematics), evaluation
• Bracket
• Term (mathematics)
• S-expression, M-expression
• Four fours
• Lookup table, mathematical table, multiplication table
• Calculator
• Counting rods
• Abacus, Chinese abacus, Roman abacus
• Torquetum
• Napier's bones, rabdology
• Slide rule
• Common logarithm
• 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
• Scholz conjecture
• Presburger arithmetic

Computability theory: models of computation

• Algorithm
• Procedure, recursion
• 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
• Myhill-Nerode theorem
• Regular expression
• Regular grammar
• Prefix grammar
• Tree automaton
• Pushdown automaton
• Context-free grammar
• Bchi automaton
• Chomsky hierarchy
• Context-sensitive language, context-sensitive grammar
• Recursively enumerable language
• Register machine
• Stack machine
• Petri net
• Post machine
• Rewriting
• Markov algorithm
• Term rewriting
• String rewriting system
• L-system
• Knuth-Bendix completion algorithm
• Star height
• Star height problem
• Generalized star height problem
• Cellular automaton
• Rule 110 cellular automaton
• Conway's Game of Life
• Langton's ant
• Edge of chaos
• Turing machine
• Deterministic Turing machine
• Non-deterministic Turing machine
• Alternating automaton
• Alternating Turing machine
• Turing-complete
• Turing tarpit
• Oracle machine
• Lambda calculus
• Combinatory logic
• Combinator
• B,C,K,W System
• Parallel computing
• Flynn's taxonomy
• Quantum computer
• Universal 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
• 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

• Exponential hierarchy
• Polynomial hierarchy

Named problems

• Clique problem
• Hamiltonian cycle problem
• Hamiltonian path problem
• Integer factorization
• Knapsack problem
• Satisfiability problem
• 2-satisfiability
• Boolean 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
• Pi-calculus
• Hypercomputation
• Real computation

<< Previous Word Browser Next >>
prince2 tadeusz br komorowski coat of arms of republika srpska nidud deep ecology (company) upper silesian metropolitan area sonic hedgehog edie bukewihge sapardi djoko damono university of indonesia rocky reach dam	after the funeral list of final fantasy characters box junction eevee vaporeon mucia tertia juan crisstomo falcn jolteon edward hunter rock island dam black backed woodpecker	wells dam flag of afghanistan wanapum dam priest rapids dam spotted crake chicha moldmaker wenatchee river little crake grand coulee dam ebbw vale	home army (disambiguation) brigid of ireland come akashic brotherhood celestial chorus book of dimma folk medicine skandinaviska banken sebakh list of towns in northern ireland foyles