This is a list of complexity class

Complexity class

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

es in 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...

. For other computational and complexity subjects, see list of computability and complexity topics.

Many of these classes have a 'Co' partner which consists of the complement

Complement (complexity)

In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement...

s of all languages in the original class. For example if a language L is in NP then the complement of L is in Co-NP. (This doesn't mean that the complement of NP is Co-NP - there are languages which are known to be in both, and other languages which are known to be in neither.)

"The hardest problems" of a class refer to problems, which belong to the class and every other problem of that class can be reduced to it. Furthermore, the reduction is also a problem of the given class, or its subset.

If you don't see a class listed (such as Co-UP) you should look under its partner (such as UP).

#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...	Count solutions to an NP problem
#P-complete	The hardest problems in #P
2-EXPTIME 2-EXPTIME In computational complexity theory, the complexity class 2-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....	Solvable with doubly exponential time
AC0 AC0 AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O and polynomial size, with unlimited-fanin AND gates and OR gates....	A circuit complexity class of bounded depth.
ACC0	A circuit complexity class of bounded depth and counting gates.
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....	A circuit complexity class.
AH	The arithmetic hierarchy
AP	The class of problems 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... s can solve in polynomial time.
APX APX In complexity theory the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant...	Optimization problem Optimization problem In 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 that have approximation algorithms with constant approximation ratio
AM Arthur-Merlin protocol In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public . This notion was introduced by...	Solvable in polynomial time by an Arthur-Merlin protocol Arthur-Merlin protocol In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public . This notion was introduced by...
BPP	Solvable in polynomial time by 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... s (answer is probably right)
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...	Solvable in polynomial time on a 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...  (answer is probably right)
co-NP	"NO" answers checkable in polynomial time by a non-deterministic machine
co-NP-complete Co-NP-complete In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that they are the ones most likely not to be in P...	The hardest problems in co-NP
DSPACE(f(n)) 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...	Solvable by a deterministic machine in space O(f(n)).
DTIME(f(n)) 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...	Solvable by a deterministic machine in time O(f(n)).
E E (complexity) In computational complexity theory, the complexity class E is the set of decision problems that can be solved by a deterministic Turing machine in time 2O and is therefore equal to the complexity class DTIME....	Solvable in exponential time with linear exponent
ELEMENTARY	The union of the classes in the exponential hierarchy
ESPACE ESPACE For the car, see Renault EspaceIn computational complexity theory, the complexity class ESPACE is the set of decision problems that can be solved by a deterministic Turing machine in space 2O.See also EXPSPACE....	Solvable in exponential space with linear exponent
EXP Exp Exp may stand for:* Exponential function, in mathematics* Expiry date of organic compounds like food or medicines* Experience points, in role-playing games* EXPTIME, a complexity class in computing* Ford EXP, a car manufactured in the 1980s...	Same as EXPTIME
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...	Solvable in exponential space
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....	Solvable with exponential time
FNP FNP (complexity) In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains:This definition does...	The analogue of NP for 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... s
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 analogue of P for function problems
FPNP	The analogue of PNP for function problems; the home of the traveling salesman problem
FPT	Fixed-parameter tractable
GapL	Logspace-reducible to computing the integer determinant of a matrix
IP 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...	Solvable in polynomial time by an 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...
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...	Solvable in logarithmic (small) space
LOGCFL LOGCFL In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language. This class is situated between NL and AC1, in the sense that it contains the former and is contained in the latter...	Logspace-reducible to a context-free language Context-free language In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
MA Arthur-Merlin protocol In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public . This notion was introduced by...	Solvable in polynomial time by a Merlin-Arthur protocol Arthur-Merlin protocol In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public . This notion was introduced by...
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...	Solvable efficiently (in polylogarithmic time) on parallel computers
NE NE (complexity) In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time O for some k....	Solvable by a non-deterministic machine in exponential time with linear exponent
NESPACE	Solvable by a non-deterministic machine in exponential space with linear exponent
NEXP	Same as NEXPTIME
NEXPSPACE	Solvable by a non-deterministic machine in exponential space
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....	Solvable by a non-deterministic machine in exponential time
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....	"YES" answers checkable in logarithmic space
NONELEMENTARY NONELEMENTARY In computational complexity theory, the complexity class NONELEMENTARY is the complement of the class ELEMENTARY.Example decidable problems in NONELEMENTARY this class are:* the problem of regular expression equivalence with not...	Complement of ELEMENTARY.
NP NP (complexity) In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...	"YES" answers checkable in polynomial time (see complexity classes P and NP)
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...	The hardest or most expressive problems in NP
NP-easy NP-easy In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP....	Analogue to PNP for 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... s; another name for FPNP
NP-equivalent NP-equivalent In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems....	The hardest problems in FPNP
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...	Either NP-complete or harder
NSPACE(f(n)) 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...	Solvable by a non-deterministic machine in space O(f(n)).
NTIME(f(n)) 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....	Solvable by a non-deterministic machine in time O(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...	Solvable in polynomial time
P-complete P-complete In complexity theory, the notion of P-complete decision problems is useful in the analysis of both:# which problems are difficult to parallelize effectively, and;# which problems are difficult to solve in limited space....	The hardest problems in P to solve on parallel computers
P/poly P/poly In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also equivalently defined as the class PSIZE of languages that have a polynomial-size circuits...	Solvable in polynomial time given an "advice string" depending only on the input size
PCP	Probabilistically Checkable Proof
PH	The union of the classes in the 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...
PNP	Solvable in polynomial time with an oracle 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...  for a problem in NP; also known as Δ2P
PP PP (complexity) In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...	Probabilistically Polynomial (answer is right with probability slightly more than ½)
PR PR (complexity) PR is the complexity class of all primitive recursive functions – or, equivalently, the set of all formal languages that can be decided by such a function...	Solvable by recursively building up arithmetic functions.
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 :...	Solvable with polynomial memory.
PSPACE-complete PSPACE-complete In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...	The hardest problems in PSPACE.
R R (complexity) In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages. R is equal to the set of all total computable functions....	Solvable in a finite amount of time.
RE RE (complexity) In computability theory and computational complexity theory, RE is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the answer is 'yes', then there is some procedure which takes finite time to...	Problems to which we can answer "YES" in a finite amount of time, but a "NO" answer might never come.
RL	Solvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right)
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...	Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
SL SL (complexity) In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...	Problems log-space reducible to determining if a path exist between given vertices in an undirected graph. In October 2004 it was discovered that this class is in fact equal to 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... .
S2P S2P (complexity) In computational complexity theory, S is a complexity class. A language L is in S_2^P if there exists a polynomial-time predicate P such that* If x \in L, then there exists a y such that for all z, P=1...	one round games with simultaneous moves refereed deterministically in polynomial time
TFNP TFNP In computational complexity theory, the complexity class TFNP is a subclass of FNP where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial."...	Total function problems solvable in non-deterministic polynomial time. A problem in this class has the property that every input has an output whose validity may be checked efficiently, and the computational challenge is to find a valid output.
UP UP (complexity) In complexity theory, UP is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input...	Unambiguous Non-Deterministic Polytime functions.
ZPP	Solvable by randomized algorithms (answer is always right, average running time is polynomial)

External links

• Complexity Zoo - list of over 400 complexity classes and their properties