Complexity class
Encyclopedia
In computational complexity theory
, a complexity class is a set of problems
of related resource-based complexity. A typical complexity class has a definition of the form:
For example, the class NP
is the set of decision problem
s whose solutions can be verified by a non-deterministic Turing machine
in polynomial time, while the class PSPACE
is the set of decision problems that can be solved by a deterministic Turing machine in polynomial space.
The simpler complexity classes are defined by the following factors:
Many complexity classes can be characterized in terms of the mathematical logic
needed to express them; see descriptive complexity
.
Bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis
states that "the time complexities in any two reasonable and general models of computation are polynomially related" . 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. The corresponding set of function problems is FP
.
The Blum axioms
can be used to define complexity classes without referring to a concrete computational model
.
It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem
.
Other important complexity classes include BPP, ZPP and RP
, which are defined using probabilistic Turing machine
s; AC
and NC
, which are defined using boolean circuits and BQP
and QMA
, which are defined using quantum Turing machines. #P
is an important complexity class of counting problems (not decision problems). Classes like IP
and AM are defined using Interactive proof system
s. ALL
is the class of all decision problems.
s or log-space reduction
s.
The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. Of course, the notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard
problems.
If a problem X is in C and hard for C, then X is said to be complete
for C. This means that X is the hardest problem in C (Since there could be many problems which are equally hard, one might say that X is one of the hardest problems in C). Thus the class of NP-complete
problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce another problem, Π1, to a known NP-complete problem, Π2, would indicate that there is no known polynomial-time solution for Π1. This is because a polynomial-time solution to Π1 would yield a polynomial-time solution to Π2. Similarly, because all NP problems can be reduced to the set, finding an NP-complete
problem that can be solved in polynomial time would mean that P = NP.
, disjunction, conjunction
, or even under all Boolean operations
. Moreover, they might also be closed under a variety of quantification schemes. P, for instance, is closed under all Boolean operations, and under quantification over polynomially sized domains. However, it is most likely not closed under quantification over exponential sized domains.
Each class X which is not closed under negation has a complement class Co-Y, which consists of the complements of the languages contained in X. Similarly one can define the Boolean closure of a class, and so on; this is however less commonly done.
One possible route to separating two complexity classes is to find some closure property possessed by one and not by the other.
of Y, then X is shown below Y, with a dark line connecting them. If X is a subset, but it is unknown whether they are equal sets, then the line is lighter and is dotted. Technically, the breakdown into decidable and undecidable pertains more to the study of computability theory
but is useful for putting the complexity classes in perspective.
More precisely, the time hierarchy theorem
states that
.
The space hierarchy theorem
states that
.
The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.
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...
, a complexity class is a set of problems
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
of related resource-based complexity. A typical complexity class has a definition of the form:
- the set of problems that can be solved by an abstract machineAbstract machineAn abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
M using OBig O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(f(n)) of resourceComputational resourceIn computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems....
R, where n is the size of the input.
For example, the class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
is the set of 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 whose solutions can be verified by a 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....
in polynomial time, while the class PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
is the set of decision problems that can be solved by a deterministic Turing machine in polynomial space.
The simpler complexity classes are defined by the following factors:
- The type of computational problem: The most commonly used problems are decision problemDecision problemIn 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. However, complexity classes can be defined based on function problemFunction problemIn 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...
s (an example is FPFP (complexity)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...
), counting problems (e.g. #PSharp-PIn computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...
), optimization problemOptimization problemIn mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
s, promise problemPromise problemIn computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs. Unlike decision problems, the yes instances and no instances do not exhaust the set of all inputs...
s, etc. - The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on nondeterministic Turing machines, boolean circuitBoolean circuitA Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...
s, quantum Turing machineQuantum Turing machineA quantum Turing machine , also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum...
s, monotone circuits, etc. - The resource (or resources) that are being bounded and the bounds: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.
Many complexity classes can be characterized in terms of the mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
needed to express them; see descriptive complexity
Descriptive complexity
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the...
.
Bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis
Cobham's Thesis
Cobham's thesis, also known as Cobham–Edmonds thesis , asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P.Formally, to say that a problem can be solved in...
states that "the time complexities in any two reasonable and general models of computation are polynomially related" . This forms the basis for the complexity class P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP
FP (complexity)
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...
.
The Blum axioms
Blum axioms
In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967....
can be used to define complexity classes without referring to a concrete computational model
Computational model
A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation. The system under study is often a complex nonlinear system for which simple, intuitive analytical solutions are...
.
Important complexity classes
Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:| Complexity class | Model of computation | Resource constraint |
|---|---|---|
| DTIME DTIME In computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm... (f(n)) |
Deterministic Turing machine | Time f(n) |
| P P (complexity) In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds... |
Deterministic Turing machine | Time poly(n) |
| EXPTIME EXPTIME In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n.... |
Deterministic Turing machine | Time 2poly(n) |
| NTIME NTIME In computational complexity theory, the complexity class NTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O, and unlimited space.... (f(n)) |
Non-deterministic Turing machine | Time f(n) |
| NP NP (complexity) In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."... |
Non-deterministic Turing machine | Time poly(n) |
| NEXPTIME NEXPTIME In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O for some polynomial p, and unlimited space.... |
Non-deterministic Turing machine | Time 2poly(n) |
| DSPACE DSPACE In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a... (f(n)) |
Deterministic Turing machine | Space f(n) |
| L L (complexity) In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space... |
Deterministic Turing machine | Space O(log n) |
| PSPACE PSPACE In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :... |
Deterministic Turing machine | Space poly(n) |
| EXPSPACE EXPSPACE In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n... |
Deterministic Turing machine | Space 2poly(n) |
| NSPACE NSPACE In computational complexity theory, the complexity class NSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine using space O, and unlimited time. It is the non-deterministic counterpart of DSPACE.Several important complexity classes can be defined in terms... (f(n)) |
Non-deterministic Turing machine | Space f(n) |
| NL NL (complexity) In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.... |
Non-deterministic Turing machine | Space O(log n) |
| NPSPACE | Non-deterministic Turing machine | Space poly(n) |
| NEXPSPACE | Non-deterministic Turing machine | Space 2poly(n) |
It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by 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,...
.
Other important complexity classes include BPP, ZPP and RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
, which are defined using 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....
s; AC
AC (complexity)
In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth O and a polynomial number of unlimited-fanin AND and OR gates....
and NC
NC (complexity)
In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...
, which are defined using boolean circuits and BQP
BQP
In computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
and QMA
QMA
In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic complexity class NP or the probabilistic complexity class MA...
, which are defined using quantum Turing machines. #P
Sharp-P
In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...
is an important complexity class of counting problems (not decision problems). Classes like IP
IP (complexity)
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985...
and AM are defined using 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...
s. ALL
ALL (complexity)
In computability and complexity theory, ALL is the class of all decision problems.-Relations to other classes:ALL contains all complexity classes of decision problems, including RE and co-RE....
is the class of all decision problems.
Reduction
Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at least as difficult as another problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we say that X reduces to Y. There are many different type of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductionPolynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
s or log-space reduction
Log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers...
s.
The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.
This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. Of course, the notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problems.
If a problem X is in C and hard for C, then X is said to be complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
for C. This means that X is the hardest problem in C (Since there could be many problems which are equally hard, one might say that X is one of the hardest problems in C). Thus the class of NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce another problem, Π1, to a known NP-complete problem, Π2, would indicate that there is no known polynomial-time solution for Π1. This is because a polynomial-time solution to Π1 would yield a polynomial-time solution to Π2. Similarly, because all NP problems can be reduced to the set, finding an NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem that can be solved in polynomial time would mean that P = NP.
Closure properties of classes
Complexity classes have a variety of closure properties; for example, decision classes may be closed under negationNegation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
, disjunction, conjunction
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
, or even under all Boolean operations
Logical connective
In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.Each logical connective can be expressed as a...
. Moreover, they might also be closed under a variety of quantification schemes. P, for instance, is closed under all Boolean operations, and under quantification over polynomially sized domains. However, it is most likely not closed under quantification over exponential sized domains.
Each class X which is not closed under negation has a complement class Co-Y, which consists of the complements of the languages contained in X. Similarly one can define the Boolean closure of a class, and so on; this is however less commonly done.
One possible route to separating two complexity classes is to find some closure property possessed by one and not by the other.
Relationships between complexity classes
The following table shows some of the classes of problems (or languages, or grammars) that are considered in complexity theory. If class X is a strict subsetSubset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of Y, then X is shown below Y, with a dark line connecting them. If X is a subset, but it is unknown whether they are equal sets, then the line is lighter and is dotted. Technically, the breakdown into decidable and undecidable pertains more to the study of 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...
but is useful for putting the complexity classes in perspective.
| |||||||||
 | | ||||||||
|
| ||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
 | |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
| | | | | |||||
| | | | | |||||
| | | | | |||||
| |
|
|
| |||||
| | | | | |||||
| | |
| | |||||
| | | | | |||||
| |
| |||||||
| | | |||||||
|
| ||||||||
| | ||||||||
| |||||||||
| |||||||||
| |||||||||
Hierarchy theorems
For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems. In particular, although DTIME(n) is contained in DTIME(n2), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved.More precisely, the 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...
states that
.The 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...
states that
.The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.
Further reading
- The Complexity Zoo: A huge list of complexity classes, as reference for experts.
- Diagram by Neil ImmermanNeil ImmermanNeil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst...
showing the hierarchy of complexity classes and how they fit together. - Michael GareyMichael GareyMichael Randolph Garey is a computer science researcher, and co-author of Computers and Intractability: A Guide to the Theory of NP-completeness. He earned his PhD in computer science in 1970 from the University of Wisconsin–Madison. In 1995 he was inducted as a Fellow of the Association for...
, and David S. JohnsonDavid S. JohnsonDavid Stifler Johnson is a computer scientist specializing in algorithms and optimization. He is currently the head of the Algorithms and Optimization Department of AT&T Labs Research. He was awarded the 2010 Knuth Prize....
: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.