This is a list of computability and complexity topics, by Wikipedia page.

Computability theory

Computability theory

Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

 is the part of the theory of computation

Computation

Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

 that deals with what can be computed, in principle. Computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

 deals with how hard computations are, in quantitative terms, both with upper bounds (algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s 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.

Calculation

Calculation

A calculation is a deliberate process for transforming one or more inputs into one or more results, with variable change.The term is used in a variety of senses, from the very definite arithmetical calculation of using an algorithm to the vague heuristics of calculating a strategy in a competition...

• Mathematical expression
  • Expression
    Expression (mathematics)
    In mathematics, an expression is a finite combination of symbols that is well-formed according to rules that depend on the context. Symbols can designate numbers , variables, operations, functions, and other mathematical symbols, as well as punctuation, symbols of grouping, and other syntactic...
    
    , evaluation
    Evaluation
    Evaluation is systematic determination of merit, worth, and significance of something or someone using criteria against a set of standards.Evaluation often is used to characterize and appraise subjects of interest in a wide range of human enterprises, including the arts, criminal justice,...
    
    
  • Bracket
    Bracket
    Brackets are tall punctuation marks used in matched pairs within text, to set apart or interject other text. In the United States, "bracket" usually refers specifically to the "square" or "box" type.-List of types:...
    
    
  • Term (mathematics)
    Term (mathematics)
    A term is a mathematical expression which may form a separable part of an equation, a series, or another expression.-Definition:In elementary mathematics, a term is either a single number or variable, or the product of several numbers or variables separated from another term by a + or - sign in an...
    
    
  • S-expression
    S-expression
    S-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages...
    
    , M-expression
    M-expression
    In computer programming, M-expressions were intended to be the expressions used to write functions in the Lisp programming language. Data to be manipulated using M-expressions was to be written using S-expressions...
    
    
  • Four fours
    Four fours
    Four fours is a mathematical puzzle. The goal of four fours is to find the simplest mathematical expression for every whole number from 0 to some maximum, using only common mathematical symbols and the digit four...
    
    
• Lookup table
  Lookup table
  In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
  
  , mathematical table
  Mathematical table
  Before calculators were cheap and plentiful, people would use mathematical tables —lists of numbers showing the results of calculation with varying arguments— to simplify and drastically speed up computation...
  
  , multiplication table
  Multiplication table
  In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system....
  
  
• Calculator
  Calculator
  An electronic calculator is a small, portable, usually inexpensive electronic device used to perform the basic operations of arithmetic. Modern calculators are more portable than most computers, though most PDAs are comparable in size to handheld calculators.The first solid-state electronic...
  
  
  • Counting rods
    Counting rods
    Counting rods are small bars, typically 3–14 cm long, used by mathematicians for calculation in China, Japan, Korea, and Vietnam. They are placed either horizontally or vertically to represent any number and any fraction....
    
    
  • Abacus
    Abacus
    The abacus, also called a counting frame, is a calculating tool used primarily in parts of Asia for performing arithmetic processes. Today, abaci are often constructed as a bamboo frame with beads sliding on wires, but originally they were beans or stones moved in grooves in sand or on tablets of...
    
    , Chinese abacus
    Chinese abacus
    thumb|Suanpan The suanpan is an abacus of Chinese origin first described in a 190 CE book of the Eastern Han Dynasty, namely Supplementary Notes on the Art of Figures written by Xu Yue...
    
    , Roman abacus
    Roman abacus
    The Romans developed the Roman hand abacus, a portable, but less capable, base-10 version of the previous Babylonian abacus. It was the first portable calculating device for engineers, merchants and presumably tax collectors...
    
    
  • Torquetum
    Torquetum
    The torquetum or turquet is a medieval astronomical instrument designed to take and convert measurements made in three sets of coordinates: Horizon, equatorial, and ecliptic...
    
    
  • Napier's bones
    Napier's bones
    Napier's bones is an abacus created by John Napier for calculation of products and quotients of numbers that was based on Arab mathematics and lattice multiplication used by Matrakci Nasuh in the Umdet-ul Hisab and Fibonacci writing in the Liber Abaci. Also called Rabdology...
    
    , rabdology
    Rabdology
    In 1617 a treatise in Latin entitled Rabdologiæ and writtenby John Napier was published in Edinburgh. Printed three yearsafter his treatise on the discovery of logarithms and in the same year...
    
    
  • Pascal's calculator
    Pascal's calculator
    Blaise Pascal invented the mechanical calculator in 1642. He conceived it while trying to help his father who had been assigned the task of reorganizing the tax revenues of the French province of Haute-Normandie ; first called Arithmetic Machine, Pascal's Calculator and later Pascaline, it could...
    
    
  • Slide rule
    Slide rule
    The slide rule, also known colloquially as a slipstick, is a mechanical analog computer. The slide rule is used primarily for multiplication and division, and also for functions such as roots, logarithms and trigonometry, but is not normally used for addition or subtraction.Slide rules come in a...
    
    
    • Common logarithm
      Common logarithm
      The common logarithm is the logarithm with base 10. It is also known as the decadic logarithm, named after its base. It is indicated by log10, or sometimes Log with a capital L...
      
      
  • Generating trigonometric tables
    Generating trigonometric tables
    In mathematics, tables of trigonometric functions are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation, science and engineering...
    
    
  • Difference engine
    Difference engine
    A difference engine is an automatic, mechanical calculator designed to tabulate polynomial functions. Both logarithmic and trigonometric functions can be approximated by polynomials, so a difference engine can compute many useful sets of numbers.-History:...
    
    
  • Analytical engine
    Analytical engine
    The Analytical Engine was a proposed mechanical general-purpose computer designed by English mathematician Charles Babbage. It was first described in 1837 as the successor to Babbage's difference engine, a design for a mechanical calculator...
    
    
  • Ada Byron's notes on the analytical engine
  • Adding machine
    Adding machine
    An adding machine was a class of mechanical calculator, usually specialized for bookkeeping calculations.In the United States, the earliest adding machines were usually built to read in dollars and cents. Adding machines were ubiquitous office equipment until they were phased out in favor of...
    
    
  • Mechanical calculator
    Mechanical calculator
    A mechanical calculator is a device used to perform the basic operations of arithmetic. Mechanical calculators are comparable in size to small desktop computers and have been rendered obsolete by the advent of the electronic calculator....
    
    
  • Comptometer
    Comptometer
    The comptometer was the first commercially successful key-driven mechanical calculator, patented in the USA by Dorr E. Felt in 1887.A key-driven calculator is extremely fast because each key adds or subtracts its value to the accumulator as soon as it is pressed and a skilled operator can enter all...
    
    
  • Differential analyser
    Differential analyser
    The differential analyser is a mechanical analogue computer designed to solve differential equations by integration, using wheel-and-disc mechanisms to perform the integration...
    
    
  • Curta calculator
    Curta calculator
    The Curta is a small, hand-cranked mechanical calculator introduced in 1948. It has an extremely compact design: a small cylinder that fits in the palm of the hand. It can be used to perform addition, subtraction, multiplication, division, and — with more difficulty — square roots and other...
    
    
  • History of computers
• Order of operations
  Order of operations
  In mathematics and computer programming, the order of operations is a rule used to clarify unambiguously which procedures should be performed first in a given mathematical expression....
  
  , infix notation
  Infix notation
  Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on . It is not as simple to parse by computers as prefix notation or postfix notation Infix notation is the common arithmetic and logical formula notation,...
  
  , reverse Polish notation
  Reverse Polish notation
  Reverse Polish notation is a mathematical notation wherein every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as Postfix notation and is parenthesis-free as long as operator arities are fixed...
  
  
• Multiplication algorithm
  Multiplication algorithm
  A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are in use...
  
  
  • Peasant multiplication
• Division by two
  Division by two
  In mathematics, division by two or halving has also been called mediation or dimidiation. The treatment of this as a different operation from multiplication and division by other numbers goes back to the ancient Egyptians, whose multiplication algorithm used division by two as one of its...
  
  
• Exponentiating by squaring
• Addition chain
  Addition chain
  In mathematics, an addition chain for computing a positive integer n can be given by a sequence of natural numbers v and a sequence of index pairs w such that each term in v is the sum of two previous terms, the indices of those terms being specified by w:Often only v is given since it is easy to...
  
  
  • Scholz conjecture
    Scholz conjecture
    In mathematics, the Scholz conjecture sometimes called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture In mathematics, the Scholz conjecture sometimes called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture In mathematics, the Scholz conjecture sometimes called the...
    
    
• Presburger arithmetic
  Presburger arithmetic
  Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely...
  
  

Computability theory: models of computation

• Arithmetic circuits
  Arithmetic circuit complexity
  In computational complexity theory, arithmetic circuits are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expression it already computed. Arithmetic circuits give us a formal...
  
  
• Algorithm
  Algorithm
  In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
  
  
  • Procedure
    Subroutine
    In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
    
    , recursion
    Recursion
    Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
    
    
• Finite state automaton
  • Mealy machine
    Mealy machine
    In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. The outputs change asynchronously with respect to the clock, meaning that the outputs change at unpredictable times, making timing analysis...
    
    
  • Minsky register machine
  • Moore machine
    Moore machine
    In the theory of computation, a Moore machine is a finite-state machine, whose output values are determined solely by its current state.-Name:The Moore machine is named after Edward F...
    
    
  • State diagram
    State diagram
    A state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, while at other times this is a reasonable abstraction...
    
    
  • State transition system
    State transition system
    In theoretical computer science, a state transition system is an abstract machine used in the study of computation. The machine consists of a set of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition...
    
    
  • Deterministic finite state machine
    Deterministic finite state machine
    In the theory of computation and automata theory, a deterministic finite state machine—also known as deterministic finite automaton —is a finite state machine accepting finite strings of symbols. For each state, there is a transition arrow leading out to a next state for each symbol...
    
    
  • Nondeterministic finite state machine
    Nondeterministic finite state machine
    In the automata theory, a nondeterministic finite state machine or nondeterministic finite automaton is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states...
    
    
  • Generalized nondeterministic finite state machine
    Generalized nondeterministic finite state machine
    In the theory of computation, a generalized nondeterministic finite state machine, also known as expression automatonor generalized nondeterministic finite automaton is an NFA where each transition is labeled with any regular expression. The GNFA reads blocks of symbols from the input which...
    
    
  • Regular language
    Regular language
    In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
    
    
    • Pumping lemma
      Pumping lemma
      In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of...
      
      
    • Myhill-Nerode theorem
  • Regular expression
    Regular expression
    In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
    
    
  • Regular grammar
    Regular grammar
    In theoretical computer science, a regular grammar is a formal grammar that describes a regular language.- Strictly regular grammars :A right regular grammar is a formal grammar such that all the production rules in P are of one of the following forms:# B → a - where B is a non-terminal in N and...
    
    
  • Prefix grammar
    Prefix grammar
    In computer science, a prefix grammar is a type of string rewriting system, consisting of a set of string rewriting rules, and similar to a formal grammar or a semi-Thue system. What is specific about prefix grammars is not the shape of their rules, but the way in which they are applied: only...
    
    
  • Tree automaton
    Tree automaton
    A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines.The following article deals with branching tree automata, which correspond to regular languages of trees...
    
    
• Pushdown automaton
  Pushdown automaton
  In automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data.- Operation :Pushdown automata differ from finite state machines in two ways:...
  
  
  • Context-free grammar
    Context-free grammar
    In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
    
    
• Büchi automaton
  Büchi automaton
  In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton that visits one of the final states infinitely often. Büchi automata recognize the...
  
  
• Chomsky hierarchy
  Chomsky hierarchy
  Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
  
  
  • Context-sensitive language
    Context-sensitive language
    In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
    
    , context-sensitive grammar
    Context-sensitive grammar
    A context-sensitive grammar is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols...
    
    
  • Recursively enumerable language
    Recursively enumerable language
    In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...
    
    
• Register machine
  Register machine
  In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine...
  
  
• Stack machine
  Stack machine
  A stack machine may be* A real or emulated computer that evaluates each sub-expression of a program statement via a pushdown data stack and uses a reverse Polish notation instruction set....
  
  
• Petri net
  Petri net
  A Petri net is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places...
  
  
• Post machine
  Post machine
  Post machine can refer to:* Post tag system* Post–Turing machine...
  
  
• Rewriting
  Rewriting
  In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. What is considered are rewriting systems...
  
  
  • Markov algorithm
    Markov algorithm
    In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation and can represent any...
    
    
  • Term rewriting
  • String rewriting system
  • L-system
    L-system
    An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms...
    
    
  • Knuth-Bendix completion algorithm
    Knuth-Bendix completion algorithm
    The Knuth–Bendix completion algorithm is an algorithm for transforming a set of equations into a confluent term rewriting system...
    
    
• Star height
  Star height
  In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexityof regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression....
  
  
  • Star height problem
    Star height problem
    The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars...
    
    
  • Generalized star height problem
    Generalized star height problem
    The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they...
    
    
• Cellular automaton
  Cellular automaton
  A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
  
  
  • Rule 110 cellular automaton
    Rule 110 cellular automaton
    The Rule 110 cellular automaton is an elementary cellular automaton with the following rule table:In the table above, when the sequence of 1s and 0s corresponding to the new states is regarded as a binary number, the decimal equivalent is 110; hence the name of the rule.-History:Around 2000,...
    
    
  • Conway's Game of Life
    Conway's Game of Life
    The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
    
    
  • Langton's ant
    Langton's ant
    Langton's ant is a two-dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000...
    
    
  • Edge of chaos
    Edge of chaos
    The phrase edge of chaos was coined by mathematician Doyne Farmer to describe the transition phenomenon discovered by computer scientist Christopher Langton. The phrase originally refers to an area in the range of a variable, λ , which was varied while examining the behavior of a cellular automaton...
    
    
• Turing machine
  Turing machine
  A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
  
  
  • Deterministic Turing machine
  • Non-deterministic Turing machine
    Non-deterministic Turing machine
    In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
    
    
  • Alternating automaton
  • Alternating Turing machine
    Alternating Turing machine
    In computational complexity theory, an alternating Turing machine is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP...
    
    
  • Turing-complete
  • Turing tarpit
    Turing tarpit
    A Turing tarpit is any programming language or computer interface that allows for a great deal of flexibility in function but is difficult to learn and use because it offers little or no support for common tasks...
    
    
  • Oracle machine
    Oracle machine
    In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
    
    
• Lambda calculus
  Lambda calculus
  In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
  
  
• Combinatory logic
  Combinatory logic
  Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
  
  
  • Combinator
    • B,C,K,W System
      B,C,K,W system
      The B, C, K, W system is a variant of combinatory logic that takes as primitive the combinators B, C, K, and W. This system was discovered by Haskell Curry in his doctoral thesis Grundlagen der kombinatorischen Logik, whose results are set out in Curry .The combinators are defined as follows:* B x...
      
      
• Parallel computing
  Parallel computing
  Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
  
  
• Flynn's taxonomy
  Flynn's Taxonomy
  Flynn's taxonomy is a classification of computer architectures, proposed by Michael J. Flynn in 1966.-Classifications:The four classifications defined by Flynn are based upon the number of concurrent instruction and data streams available in the architecture:Single Instruction, Single Data stream...
  
  
• Quantum computer
  Quantum computer
  A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
  
  
  • Universal quantum computer
• Church-Turing thesis
  • Recursive function
    Recursive function
    Recursive function may refer to:*Recursion , a procedure or subroutine, implemented in a programming language, whose implementation references itself*A total computable function, a function which is defined for all possible inputs...
    
    

Decision problem

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

s

• Entscheidungsproblem
  Entscheidungsproblem
  In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
  
  
• Halting problem
  Halting problem
  In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
  
  
  • Correctness
    Correctness
    In theoretical computer science, correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification...
    
    
• Post correspondence problem
  Post correspondence problem
  The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability....
  
  
• Decidable language
  • Undecidable language
• Word problem for groups
  Word problem for groups
  In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element...
  
  
• Wang tile
  Wang tile
  Wang tiles , first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems...
  
  
• Penrose tiling
  Penrose tiling
  A Penrose tiling is a non-periodic tiling generated by an aperiodic set of prototiles named after Sir Roger Penrose, who investigated these sets in the 1970s. The aperiodicity of the Penrose prototiles implies that a shifted copy of a Penrose tiling will never match the original...
  
  

Definability questions

• Computable number
  Computable number
  In mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm...
  
  
• Definable number
  Definable number
  A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ holds in the standard model of set theory .For the purposes of this article,...
  
  
• Halting probability
• Algorithmic information theory
  Algorithmic information theory
  Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...
  
  
• Algorithmic probability
  Algorithmic probability
  In algorithmic information theory, algorithmic probability is a method of assigning a probability to each hypothesis that explains a given observation, with the simplest hypothesis having the highest probability and the increasingly complex hypotheses receiving increasingly small probabilities...
  
  
• Data compression
  Data compression
  In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
  
  

Complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

• Advice (complexity)
  Advice (complexity)
  In computational complexity theory, an advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself...
  
  
• Amortized analysis
  Amortized analysis
  In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
  
  
• Arthur–Merlin protocol
• Best and worst cases
• Busy beaver
  Busy beaver
  In computability theory, a busy beaver is a Turing machine that attains the maximum "operational busyness" among all the Turing machines in a certain class...
  
  
• Circuit complexity
  Circuit complexity
  In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
  
  
• Constructible function
  Constructible function
  In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f can be constructed from n by a Turing machine in the time of order f...
  
  
• Cook's theorem
  Cook's theorem
  In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete...
  
  
• Exponential time
• Function problem
  Function problem
  In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
  
  
• Linear time
• Linear speedup theorem
• Natural proof
  Natural proof
  In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown that no such proof can possibly be used to solve the P vs...
  
  
• Polynomial time
• Polynomial-time many-one reduction
• Polynomial-time Turing reduction
• Savitch's theorem
  Savitch's theorem
  In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
  
  
• Space hierarchy theorem
  Space hierarchy theorem
  In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems...
  
  
• Speed Prior
  Speed prior
  Jürgen Schmidhuber's speed prior is a complexity measure similar to Kolmogorov complexity, except that it is based on computation speed as well as programlength.The speed prior complexity of a program is its...
  
  
• Speedup theorem
  Speedup theorem
  In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a more efficient algorithm solving the same problem....
  
  
• Subquadratic time
• Time hierarchy theorem
  Time hierarchy theorem
  In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems...
  
  

Complexity classes

See the list of complexity classes

• Exponential hierarchy
• Polynomial hierarchy
  Polynomial hierarchy
  In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
  
  

Named problems

• Clique problem
  Clique problem
  In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
  
  
• Hamiltonian cycle problem
• Hamiltonian path problem
  Hamiltonian path problem
  In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
  
  
• Integer factorization
  Integer factorization
  In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
  
  
• Knapsack problem
  Knapsack problem
  The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
  
  
• Satisfiability problem
  • 2-satisfiability
    2-satisfiability
    In computer science, 2-satisfiability is the problem of determining whether a collection of two-valued variables with constraints on pairs of variables can be assigned values satisfying all the constraints...
    
    
  • Boolean satisfiability problem
    Boolean satisfiability problem
    In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
    
    
• Subset sum problem
• 3SUM
  3SUM
  In computational complexity theory, 3SUM is the following computational problem conjectured to require roughly quadratic time:There is a simple algorithm to solve 3SUM in O time. This is the fastest algorithm known in models that do not decompose the integers into bits, but matching lower bounds...
  
  
• Traveling salesman problem
• Vertex cover problem
• One way function
• Set cover problem
  Set cover problem
  The set covering problem is a classical question in computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms...
  
  
• Independent set problem

Extensions

• Probabilistic algorithm, randomized algorithm
  Randomized algorithm
  A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
  
  
• Las Vegas algorithm
  Las Vegas algorithm
  In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the verity of the result; it gambles only with the resources...
  
  
• Non-determinism
• Non-deterministic Turing machine
  Non-deterministic Turing machine
  In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
  
  
• Interactive computation
  Interactive computation
  In computer science, interactive computation is a mathematical model for computation that involves communication with the external world during the computation...
  
  
• Interactive proof system
  Interactive proof system
  In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
  
  
• Probabilistic Turing Machine
  Probabilistic Turing machine
  In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution....
  
  
• Approximation algorithm
  Approximation algorithm
  In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
  
  
• Simulated annealing
  Simulated annealing
  Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
  
  
• Ant colony algorithm
• Game semantics
  Game semantics
  Game semantics is an approach to formal semantics that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player, somewhat resembling Socratic dialogues or medieval theory of Obligationes. In the late 1950s Paul Lorenzen was the...
  
  
• Generalized game
  Generalized game
  In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. For example, generalized chess is the game of chess played on an n-by-n board, with 2n pieces on each side.Complexity theory studies the asymptotic difficulty...
  
  
• Multiple-agent system
• Parameterized complexity
  Parameterized complexity
  Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
  
  
• Process calculi
  • Pi-calculus
    Pi-calculus
    In theoretical computer science, the π-calculus is a process calculus originally developed by Robin Milner, and David Walker as a continuation of work on the process calculus CCS...
    
    
• Hypercomputation
  Hypercomputation
  Hypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
  
  
• Real computation
  Real computation
  In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. They are given this name because they operate on the set of real numbers...