List of complexity classes

Last updated February 07, 2023

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.

#P	Count solutions to an NP problem
#P-complete	The hardest problems in #P
2-EXPTIME	Solvable in doubly exponential time
AC⁰	A circuit complexity class of bounded depth
ACC⁰	A circuit complexity class of bounded depth and counting gates
AC	A circuit complexity class
AH	The arithmetic hierarchy
AP	The class of problems alternating Turing machines can solve in polynomial time.^[1]
APX	Optimization problems that have approximation algorithms with constant approximation ratio^[1]
AM	Solvable in polynomial time by an Arthur–Merlin protocol ^[1]
BPP	Solvable in polynomial time by randomized algorithms (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
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)).
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	The analogue of NP for function problems
FP	The analogue of P for function problems
FP^NP	The analogue of P^NP 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	Solvable in polynomial time by an interactive proof system
L	Solvable with logarithmic (small) space
LOGCFL	Logspace-reducible to a context-free language
MA	Solvable in polynomial time by a Merlin–Arthur protocol
NC	Solvable efficiently (in polylogarithmic time) on parallel computers
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	"YES" answers checkable with logarithmic space
NONELEMENTARY	Complement of ELEMENTARY.
NP	"YES" answers checkable in polynomial time (see complexity classes P and NP)
NP-complete	The hardest or most expressive problems in NP
NP-easy	Analogue to P^NP for function problems; another name for FP^NP
NP-equivalent	The hardest problems in FP^NP
NP-hard	At 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)).
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
PCP	Probabilistically Checkable Proof
PH	The union of the classes in the polynomial hierarchy
P^NP	Solvable in polynomial time with an oracle for a problem in NP; also known as Δ₂P
PP	Probabilistically Polynomial (answer is right with probability slightly more than ½)
PPAD	Polynomial Parity Arguments on Directed graphs
PR	Solvable by recursively building up arithmetic functions.
PSPACE	Solvable with polynomial space.
PSPACE-complete	The 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.
R	Solvable in a finite amount of time.
RE	Problems to which we can answer "YES" in a finite amount of time, but a "NO" answer might never come.
RL	Solvable with logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right)
RP	Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
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.
S₂P	one round games with simultaneous moves refereed deterministically in polynomial time^[2]
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	Unambiguous Non-Deterministic Polytime functions.
ZPL	Solvable by randomized algorithms (answer is always right, average space usage is logarithmic)
ZPP	Solvable by randomized algorithms (answer is always right, average running time is polynomial)

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if only no-instances have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly.

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:

In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second.

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

In complexity theory, UP is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input. UP contains P and is contained in NP.

In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.

In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof, as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.

In computational complexity theory, P, also known as PTIME or DTIME(n^O), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

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. The complexity class was defined by Gill in 1977.

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

In computational complexity theory, NL is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

In computational complexity theory, a language B is said to be low for a complexity class A if A^B = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines which can solve problems in A, but are “easy to solve”. An A machine can simulate many oracle queries to B without exceeding its resource bounds.

In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE(s ) = co-NSPACE(s ) for any function s(n) ≥ log n. The result is equivalently stated as NL = co-NL; although this is the special case when s(n) = log n, it implies the general theorem by a standard padding argument. The result solved the second LBA problem.

In computational complexity theory, a problem is NP-complete when:

it is a problem for which the correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

References

1 2 3 Sanjeev Arora, Boaz Barak (2009), Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, ISBN 978-0-521-42426-4
↑ "S₂P: Second Level of the Symmetric Hierarchy". Stanford University Complexity Zoo. Archived from the original on 2012-10-14. Retrieved 2011-10-27.

External links

Complexity Zoo - list of over 500 complexity classes and their properties

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[complex-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] "S₂P: Second Level of the Symmetric Hierarchy". Stanford University Complexity Zoo. Archived from the original on 2012-10-14. Retrieved 2011-10-27.

[1]

[2]