Editing List of complexity classes (section)

{{Short description|none}}
{{More citations needed|date=April 2010}}
[[Image:Complexity subsets pspace.svg|thumb|right|A representation of the relation among complexity classes]]
This is a '''list of [[complexity class]]es''' 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 [[complement (complexity)|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 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.

{|
|[[Sharp-P|#P]]||Count solutions to an NP problem
|-
|[[Sharp-P-complete|#P-complete]]||The hardest problems in #P
|-
|[[2-EXPTIME]]||Solvable in doubly exponential time
|-
|[[AC0|AC<sup>0</sup>]]||A circuit complexity class of bounded depth
|-
|[[ACC0|ACC<sup>0</sup>]]||A circuit complexity class of bounded depth and counting gates
|-
|[[AC (complexity)|AC]]||A circuit complexity class
|-
|[[AH (complexity)|AH]]||The arithmetic hierarchy
|-
|[[AP (complexity)|AP]]||The class of problems [[alternating Turing machine]]s can solve in polynomial time.<ref name=complex>{{citation
|title=Computational Complexity: A Modern Approach |author=Sanjeev Arora, Boaz Barak
|publisher= Cambridge University Press; 1 edition |year=2009
|isbn=978-0-521-42426-4
}}</ref>
|-
|[[APX]]||[[Optimization problem]]s that have approximation algorithms with constant approximation ratio<ref name=complex/>
|-
|[[Arthur–Merlin protocol|AM]]||Solvable in polynomial time by an [[Arthur–Merlin protocol]]<ref name=complex/>
|-
|[[Bounded-error probabilistic polynomial|BPP]]||Solvable in polynomial time by [[randomized algorithm]]s (answer is probably right)
|-
|[[BQP]]||Solvable 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-complete]]||The hardest problems in co-NP
|-
|[[DLIN]]||Solvable by a deterministic multitape Turing machine in time ''O''(''n'').
|-
|[[DSPACE|DSPACE(''f''(''n''))]]||Solvable by a deterministic machine with space ''O''(''f''(''n'')).
|-
|[[DTIME|DTIME(''f''(''n''))]]||Solvable by a deterministic machine in time ''O''(''f''(''n'')).
|-
|[[E (complexity)|E]]||Solvable in exponential time with linear exponent
|-
|[[ELEMENTARY]]||The union of the classes in the [[exponential hierarchy]]
|-
|[[ESPACE]]||Solvable with exponential space with linear exponent
|-
|[[EXP]]||Same as EXPTIME
|-
|[[EXPSPACE]]||Solvable with exponential space
|-
|[[EXPTIME]]||Solvable in exponential time
|-
|[[FNP (complexity)|FNP]]||The analogue of NP for [[function problem]]s
|-
|[[FP (complexity)|FP]]||The analogue of P for function problems
|-
|FP<sup>NP</sup>||The analogue of P<sup>NP</sup> for function problems; the home of the [[traveling salesman problem]]
|-
|[[Fixed-parameter tractable|FPT]]||Fixed-parameter tractable
|-
|GapL|| Logspace-reducible to computing the integer determinant of a matrix
|-
|[[Interactive proof system|IP]]||Solvable in polynomial time by an [[interactive proof system]]
|-
|[[L (complexity)|L]]||Solvable with logarithmic (small) space
|-
|[[LOGCFL]] || Logspace-reducible to a [[context-free language]]
|-
|[[Arthur–Merlin protocol|MA]]||Solvable in polynomial time by a [[Arthur–Merlin protocol|Merlin–Arthur protocol]]
|-
|[[NC (complexity)|NC]]||Solvable efficiently (in polylogarithmic time) on parallel computers
|-
|[[NE (complexity)|NE]]||Solvable by a non-deterministic machine in exponential time with linear exponent
|-
|[[NESPACE]]||Solvable by a non-deterministic machine with exponential space with linear exponent
|-
|[[NEXP]]||Same as NEXPTIME
|-
|[[NEXPSPACE]]||Solvable by a non-deterministic machine with exponential space
|-
|[[NEXPTIME]]||Solvable by a non-deterministic machine in exponential time
|-
|[[NL (complexity)|NL]]||"YES" answers checkable with logarithmic space
|-
|[[NLIN]]||Solvable by a nondeterministic multitape Turing machine in time ''O''(''n'').
|-
|[[NONELEMENTARY]]||Complement of [[ELEMENTARY]].
|-
|[[NP (complexity)|NP]]||"YES" answers checkable in polynomial time (see [[P = NP problem|complexity classes P and NP]])
|-
|[[NP-complete]]||The hardest or most expressive problems in NP
|-
|[[NP-easy]]||Analogue to P<sup>NP</sup> for [[function problem]]s; another name for FP<sup>NP</sup>
|-
|[[NP-equivalent]]||The hardest problems in FP<sup>NP</sup>
|-
|[[NP-hard]]||At least as hard as every problem in NP but not known to be in the same complexity class
|-
|[[NSPACE|NSPACE(''f''(''n''))]]||Solvable by a non-deterministic machine with space ''O''(''f''(''n'')).
|-
|[[NTIME|NTIME(''f''(''n''))]]||Solvable by a non-deterministic machine in time ''O''(''f''(''n'')).
|-
|[[P (complexity)|P]]||Solvable in polynomial time
|-
|[[P-complete]]||The hardest problems in P to solve on parallel computers
|-
|[[P/poly]]||Solvable in polynomial time given an "advice string" depending only on the input size
|-
|[[probabilistically checkable proof|PCP]]||Probabilistically Checkable Proof
|-
|[[PH (complexity)|PH]]||The union of the classes in the [[polynomial hierarchy]]
|-
|P<sup>NP</sup>||Solvable in polynomial time with an [[oracle machine|oracle]] for a problem in NP; also known as Δ<sub>2</sub>P
|-
|[[PP (complexity)|PP]]||Probabilistically Polynomial (answer is right with probability slightly more than 1/2)
|-
|[[PPAD (complexity)|PPAD]]|| Polynomial Parity Arguments on Directed graphs
|-
|[[PR (complexity)|PR]]||Solvable by recursively building up arithmetic functions.
|-
|[[PSPACE]]||Solvable with polynomial space.
|-
|[[PSPACE-complete]]||The hardest problems in PSPACE.
|-
|[[Polynomial-time approximation scheme|PTAS]]|| Polynomial-time approximation scheme (a subclass of APX).
|-
|[[QIP (complexity)|QIP]]|| Solvable in polynomial time by a quantum interactive proof system.
|-
|[[QMA]]|| Quantum analog of [[NP (complexity)|NP]].
|-
|[[R (complexity)|R]]||Solvable in a finite amount of time.
|-
|[[RE (complexity)|RE]]||Problems to which we can answer "YES" in a finite amount of time, but a "NO" answer might never come.
|-
|[[RL (complexity)|RL]]||Solvable with logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right)
|-
|[[RP (complexity)|RP]]||Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
|-
|[[SL (complexity)|SL]]||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 (complexity)|L]].
|-
|[[S2P (complexity)|S<sub>2</sub>P]]||one round games with simultaneous moves refereed deterministically in polynomial time<ref>{{cite web|title=S<sub>2</sub>P: Second Level of the Symmetric Hierarchy|url=http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#s2p|publisher=Stanford University Complexity Zoo|access-date=2011-10-27|archive-url=https://web.archive.org/web/20121014045404/http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#s2p|archive-date=2012-10-14|url-status=dead}}</ref>
|-
|[[TFNP]]||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 (complexity)|UP]]||Unambiguous Non-Deterministic Polytime functions.
|-
|[[ZPL (complexity)|ZPL]]||Solvable by randomized algorithms (answer is always right, average space usage is logarithmic)
|-
|[[ZPP (complexity)|ZPP]]||Solvable by randomized algorithms (answer is always right, average running time is polynomial)
|}