Computational complexity theory

computational complexitycomplexity theorycomplexityintractableasymptotic complexitycomputationally intractableintractabilitytractabletractable problemtime complexity
Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other.wikipedia
812 Related Articles

Model of computation

models of computationmodelmodels of computing
The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage.
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input.

Travelling salesman problem

traveling salesman problemTSPtraveling salesman
To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities?
In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems.

Computational complexity

complexitycomputational burdenamount of computation
The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage.
The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Computability theory

recursion theorycomputablecomputability
Closely related fields in theoretical computer science are analysis of algorithms and computability theory.
Although there is considerable overlap in terms of knowledge and methods, mathematical recursion theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages.

Analysis of algorithms

computational complexitycomplexity analysiscomputationally expensive
Closely related fields in theoretical computer science are analysis of algorithms and computability theory.
Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem.

P versus NP problem

P = NPP ≠ NPP=NP
The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.
The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem.

Decision problem

decision procedureundecidabledecision problems
Decision problems are one of the central objects of study in computational complexity theory. A function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no.
In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

Function problem

FPfunction problems
A function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no.
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem.

Communication complexity

Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.
Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob.

Algorithm

algorithmsalgorithm designcomputer algorithm
A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
Van Emde Boas observes "even if we base complexity theory on abstract instead of concrete machines, arbitrariness of the choice of a model remains. It is at this point that the notion of simulation enters".

Formal language

formal language theoryformal languageslanguage
A decision problem can be viewed as a formal language, where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no.
In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines with limited computational power.

Alternating Turing machine

alternationalternating Turing machinesexistential state
Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines.
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.

Church–Turing thesis

Church-Turing thesisChurch's thesisTuring's Thesis
Indeed, this is the statement of the Church–Turing thesis.
These variations are not due to Church or Turing, but arise from later work in complexity theory and digital physics.

DTIME

deterministicDTIME(f(''n''))DTIME(f(n))
For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).
In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine.

Decision tree model

algebraic decision treequery complexitydecision tree complexity
Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.
In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of branching operations based on comparisons of some quantities, the comparisons being assigned unit computational cost.

Turing machine

deterministic Turing machineTuring machinesuniversal computer
Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines.
Studying their abstract properties yields many insights into computer science and complexity theory.

P (complexity)

Ppolynomial timePTIME
This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time.
In computational complexity theory, P, also known as PTIME or DTIME(n O(1) ), is a fundamental complexity class.

Big O notation

Obig-O notationlittle-o notation
The complexity of an algorithm is often expressed using big O notation.
In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

Complexity

complexdetailcomplexity theory
Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource.
Ho and Basu present a set of complexity measures for binary classification problems.

Boolean circuit

Boolean circuitscircuitcircuits
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for digital logic circuits.

Counting problem (complexity)

counting problemcounting problemscounting complexity
In computational complexity theory and computability theory, a counting problem is a type of computational problem.

BPP (complexity)

BPPBounded-error Probabilistic Polynomialbounded error probability in polynomial time
Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using Boolean circuits; and BQP and QMA, which are defined using quantum Turing machines.
In computational complexity theory, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances.

FP (complexity)

FPthe class of polynomial-time functions
The corresponding set of function problems is FP.
In computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P.

Circuit complexity

non-uniformcircuitmonotone circuit
Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree 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.

Promise problem

promisedPromise-UPrestricted
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs.