List of complexity classes

This is a list of complexity classes in computational complexity theory. 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 complements 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 does not 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 such that 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.

#PCount solutions to an NP problem
#P-completeThe hardest problems in #P
2-EXPTIMESolvable in doubly exponential time
AC0A circuit complexity class of bounded depth.
ACC0A circuit complexity class of bounded depth and counting gates.
ACA circuit complexity class.
AHThe arithmetic hierarchy
APThe class of problems alternating Turing machines can solve in polynomial time.[1]
APXOptimization problems that have approximation algorithms with constant approximation ratio[1]
AMSolvable in polynomial time by an Arthur-Merlin protocol[1]
BPPSolvable in polynomial time by randomized algorithms (answer is probably right)
BQPSolvable in polynomial time on a quantum computer (answer is probably right)
co-NP"NO" answers checkable in polynomial time by a non-deterministic machine
co-NP-completeThe hardest problems in co-NP
DSPACE(f(n))Solvable by a deterministic machine with space O(f(n)).
DTIME(f(n))Solvable by a deterministic machine in time O(f(n)).
ESolvable in exponential time with linear exponent
ELEMENTARYThe union of the classes in the exponential hierarchy
ESPACESolvable with exponential space with linear exponent
EXPSame as EXPTIME
EXPSPACESolvable with exponential space
EXPTIMESolvable in exponential time
FNPThe analogue of NP for function problems
FPThe analogue of P for function problems
FPNPThe analogue of PNP for function problems; the home of the traveling salesman problem
FPTFixed-parameter tractable
GapL Logspace-reducible to computing the integer determinant of a matrix
IPSolvable in polynomial time by an interactive proof system
LSolvable with logarithmic (small) space
LOGCFL Logspace-reducible to a context-free language
MASolvable in polynomial time by a Merlin-Arthur protocol
NCSolvable efficiently (in polylogarithmic time) on parallel computers
NESolvable by a non-deterministic machine in exponential time with linear exponent
NESPACESolvable by a non-deterministic machine with exponential space with linear exponent
NEXPSame as NEXPTIME
NEXPSPACESolvable by a non-deterministic machine with exponential space
NEXPTIMESolvable by a non-deterministic machine in exponential time
NL"YES" answers checkable with logarithmic space
NONELEMENTARYComplement of ELEMENTARY.
NP"YES" answers checkable in polynomial time (see complexity classes P and NP)
NP-completeThe hardest or most expressive problems in NP
NP-easyAnalogue to PNP for function problems; another name for FPNP
NP-equivalentThe hardest problems in FPNP
NP-hardAt least as hard as every problem in NP but not known to be in the same complexity class
NSPACE(f(n))Solvable by a non-deterministic machine with space O(f(n)).
NTIME(f(n))Solvable by a non-deterministic machine in time O(f(n)).
PSolvable in polynomial time
P-completeThe hardest problems in P to solve on parallel computers
P/polySolvable in polynomial time given an "advice string" depending only on the input size
PCPProbabilistically Checkable Proof
PHThe union of the classes in the polynomial hierarchy
PNPSolvable in polynomial time with an oracle for a problem in NP; also known as Δ2P
PPProbabilistically Polynomial (answer is right with probability slightly more than ½)
PPAD Polynomial Parity Arguments on Directed graphs
PRSolvable by recursively building up arithmetic functions.
PSPACESolvable with polynomial space.
PSPACE-completeThe hardest problems in PSPACE.
PTAS Polynomial-time approximation scheme (a subclass of NP).
RSolvable in a finite amount of time.
REProblems to which we can answer "YES" in a finite amount of time, but a "NO" answer might never come.
RLSolvable with logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right)
RPSolvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
SLProblems 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.
S2Pone round games with simultaneous moves refereed deterministically in polynomial time[2]
TFNPTotal 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.
UPUnambiguous Non-Deterministic Polytime functions.
ZPLSolvable by randomized algorithms (answer is always right, average space usage is logarithmic)
ZPPSolvable by randomized algorithms (answer is always right, average running time is polynomial)

References

  1. 1 2 3 Sanjeev Arora, Boaz Barak (2009), Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, ISBN 978-0-521-42426-4
  2. "S2P: Second Level of the Symmetric Hierarchy". Stanford University Complexity Zoo.

External links

This article is issued from Wikipedia - version of the 8/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.