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.
#PCount solutions to an NP problem#P-completeThe hardest problems in #P2-EXPTIMESolvable in doubly exponential timeAC0A circuit complexity class of bounded depthACC0A circuit complexity class of bounded depth and counting gatesACA circuit complexity classAHThe arithmetic hierarchyAPThe class of problems alternating Turing machines can solve in polynomial time.APXOptimization problems that have approximation algorithms with constant approximation ratioAMSolvable in polynomial time by an Arthur–Merlin protocolBPPSolvable in polynomial time by randomized algorithms (answer is probably right)BPLproblems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided errorBQPSolvable in polynomial time on a quantum computer (answer is probably right)co-NP"NO" answers checkable in polynomial time by a non-deterministic machineco-NP-completeThe hardest problems in co-NPDLINSolvable by a deterministic multitape Turing machine in time O(n).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 exponentELEMENTARYThe union of the classes in the exponential hierarchyESPACESolvable with exponential space with linear exponentEXPSame as EXPTIMEEXPSPACESolvable with exponential spaceEXPTIMESolvable in exponential timeFNPThe analogue of NP for function problemsFPThe analogue of P for function problemsFPNPThe analogue of PNP for function problems; the home of the traveling salesman problemFPTFixed-parameter tractableGapL Logspace-reducible to computing the integer determinant of a matrixIPSolvable in polynomial time by an interactive proof systemLSolvable with logarithmic (small) spaceLOGCFL Logspace-reducible to a context-free languageMASolvable in polynomial time by a Merlin–Arthur protocolNCSolvable efficiently (in polylogarithmic time) on parallel computersNESolvable by a non-deterministic machine in exponential time with linear exponentNESPACESolvable by a non-deterministic machine with exponential space with linear exponentNEXPSame as NEXPTIMENEXPSPACESolvable by a non-deterministic machine with exponential spaceNEXPTIMESolvable by a non-deterministic machine in exponential timeNL"YES" answers checkable with logarithmic spaceNLINSolvable by a nondeterministic multitape Turing machine in time O(n).NONELEMENTARYComplement of ELEMENTARY.NP"YES" answers checkable in polynomial time (see complexity classes P and NP)NP-completeThe hardest or most expressive problems in NPNP-easyAnalogue to PNP for function problems; another name for FPNPNP-equivalentThe hardest problems in FPNPNP-hardAt least as hard as every problem in NP but not known to be in the same complexity classNSPACE(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 timeP-completeThe hardest problems in P to solve on parallel computersP/polySolvable in polynomial time given an "advice string" depending only on the input sizePCPProbabilistically Checkable ProofPHThe union of the classes in the polynomial hierarchyPLsolvable in polynomial time with a logarithmic space randomized machine with probability > 1⁄2PNPSolvable in polynomial time with an oracle for a problem in NP; also known as Δ2PPPProbabilistically Polynomial (answer is right with probability slightly more than 1/2)PPAD Polynomial Parity Arguments on Directed graphsPRSolvable by recursively building up arithmetic functions.PSPACESolvable with polynomial space.PSPACE-completeThe hardest problems in PSPACE.PTAS Polynomial-time approximation scheme (a subclass of APX).QIP Solvable in polynomial time by a quantum interactive proof system.QMA Quantum analog 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 timeTFNPTotal 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
External links Complexity Zoo - list of over 500 complexity classes and their properties