This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics. In computational complexity theory, a complexity class is a set of problems of related complexity. ... As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ... This is a list of computability and complexity topics, by Wikipedia page. ...

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 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.) In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. ...

"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).

The title given to this article is incorrect due to technical limitations. ... The title given to this article is incorrect due to technical limitations. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time (either of these machine types determines the same class). ... In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer... In complexity theory the class APX (an abbreviation of approximable) is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short). ... In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ... In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifiers coin tosses are constrained to be public (i. ... In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifiers coin tosses are constrained to be public (i. ... This article is about the complexity class. ... A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. ... BQP, in computational complexity theory, stands for Bounded error, Quantum, Polynomial time. It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances. ... The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers. ... In computational complexity theory, co-NP is a complexity class. ... In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem... DSpace is an open source software package which provides the tools for management of digital assets, and is commonly used as the basis for an institutional repository. ... In computational complexity theory, the complexity class DTIME(f(n)) or TIME(f(n)) is the set of decision problems that can be solved by a deterministic Turing machine using time O(f(n)), and unlimited space. ... 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 O(kn) for some k. ... In computational complexity theory, the complexity class ELEMENTARY is the union of the classes in the exponential hierarchy. ... In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, starting with EXP: and continuing with and so on. ... In 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(n). ... Exp, in Role-Playing Games, stands for experience points. ... In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is a bit of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains: A binary relation P(x,y... In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem... 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. Roughly speaking, it is the class of functions that can be efficiently... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ... In computer science, fixed-parameter algorithms are an approach to attacking NP-hard problems. ... In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. ... In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. ... 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. ... 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. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifiers coin tosses are constrained to be public (i. ... In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifiers coin tosses are constrained to be public (i. ... In complexity theory, the class NC (Nicks Class) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. ... 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(kn) for some k. ... In computational complexity theory, the complexity class NESPACE is the set of decision problems that can be solved by a non-deterministic Turing machine in space O(2n). ... In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2p(n)) for some polynomial p(n), and unlimited space. ... In computational complexity theory, the complexity class NEXPSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine in space O(2p(n)) for some polynomial function p(n). ... In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2p(n)) for some polynomial p(n), and unlimited space. ... 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. ... 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 decision problem for monadic second-order logic over trees decision problem for term algebras Categories: Complexity classes ... In computational complexity theory, the complexity class ELEMENTARY is the union of the classes in the exponential hierarchy. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP-complete in this case was established by Ladner. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... 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. In other words, a problem X is NP-easy if and only if there exists some... In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem... In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. ... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In computational complexity theory, the complexity class NSPACE(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine using space O(f(n)), and unlimited time. ... In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(f(n)), and unlimited space. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. ... P/Poly is the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. ... In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has... 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. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ... 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. ... 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. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In complexity theory, PSPACE-complete is a complexity class. ... The class of decision problems solvable by a Turing machine. ... RE (recursively enumerable) is the class of decision problems for which a yes answer can be verified by a Turing machine in a finite amount of time. ... This article is about the complexity class; for the acronym used on the Internet, see real life. ... In complexity theory, RP (randomized polynomial time) 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 If the correct answer is NO, it always returns NO If the correct answer is YES, then... tsIn computational complexity theory, RLP is the complexity class of problems solvable in logarithmithic space and polynomial time with probabilistic Turing machines that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called one-sided error. ... In computational complexity theory, SL (Symmetric Logspace) 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 same... 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. ... In complexity theory, UP (Unambiguous Non-deterministic Polynomial-time) 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. ... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ...

External link

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