While deterministic and non-deterministic
Turing machines are the most commonly used models of computation, many complexity classes are defined in terms of other computational models. In particular, • A number of classes are defined using
probabilistic Turing machines, including the classes
BPP,
PP,
RP, and
ZPP • A number of classes are defined using
interactive proof systems, including the classes
IP,
MA, and
AM • A number of classes are defined using
Boolean circuits, including the classes
P/poly and its subclasses
NC and
AC • A number of classes are defined using
quantum Turing machines, including the classes
BQP and
QMA These are explained in greater detail below.
Randomized computation A number of important complexity classes are defined using the
probabilistic Turing machine, a variant of the
Turing machine that can toss random coins. These classes help to better describe the complexity of
randomized algorithms. A probabilistic Turing machine is similar to a deterministic Turing machine, except rather than following a single transition function (a set of rules for how to proceed at each step of the computation) it probabilistically selects between multiple transition functions at each step. The standard definition of a probabilistic Turing machine specifies two transition functions, so that the selection of transition function at each step resembles a coin flip. The randomness introduced at each step of the computation introduces the potential for error; that is, strings that the Turing machine is meant to accept may on some occasions be rejected and strings that the Turing machine is meant to reject may on some occasions be accepted. As a result, the complexity classes based on the probabilistic Turing machine are defined in large part around the amount of error that is allowed. Formally, they are defined using an error probability \epsilon. A probabilistic Turing machine M is said to recognize a language L with error probability \epsilon if: • a string w in L implies that \text{Pr}[M \text{ accepts } w] \geq 1 - \epsilon • a string w not in L implies that \text{Pr}[M \text{ rejects } w] \geq 1 - \epsilon
Important complexity classes class and is described in the quantum computing section. The fundamental randomized time complexity classes are
ZPP,
RP,
co-RP,
BPP, and
PP. The strictest class is
ZPP (zero-error probabilistic polynomial time), the class of problems solvable in polynomial time by a probabilistic Turing machine with error probability 0. Intuitively, this is the strictest class of probabilistic problems because it demands
no error whatsoever. A slightly looser class is
RP (randomized polynomial time), which maintains no error for strings not in the language but allows bounded error for strings in the language. More formally, a language is in
RP if there is a probabilistic polynomial-time Turing machine M such that if a string is not in the language then M always rejects and if a string is in the language then M accepts with a probability at least 1/2. The class
co-RP is similarly defined except the roles are flipped: error is not allowed for strings in the language but is allowed for strings not in the language. Taken together, the classes
RP and
co-RP encompass all of the problems that can be solved by probabilistic Turing machines with
one-sided error. Loosening the error requirements further to allow for
two-sided error yields the class
BPP (bounded-error probabilistic polynomial time), the class of problems solvable in polynomial time by a probabilistic Turing machine with error probability less than 1/3 (for both strings in the language and not in the language).
BPP is the most practically relevant of the probabilistic complexity classes—problems in
BPP have efficient
randomized algorithms that can be run quickly on real computers.
BPP is also at the center of the important unsolved problem in computer science over whether
P=BPP, which if true would mean that randomness does not increase the computational power of computers, i.e. any probabilistic Turing machine could be simulated by a deterministic Turing machine with at most polynomial slowdown. The broadest class of efficiently-solvable probabilistic problems is
PP (probabilistic polynomial time), the set of languages solvable by a probabilistic Turing machine in polynomial time with an error probability of less than 1/2 for all strings.
ZPP,
RP and
co-RP are all subsets of
BPP, which in turn is a subset of
PP. The reason for this is intuitive: the classes allowing zero error and only one-sided error are all contained within the class that allows two-sided error, and
PP simply relaxes the error probability of
BPP.
ZPP relates to
RP and
co-RP in the following way: \textsf{ZPP}=\textsf{RP}\cap\textsf{co-RP}. That is,
ZPP consists exactly of those problems that are in both
RP and
co-RP. Intuitively, this follows from the fact that
RP and
co-RP allow only one-sided error:
co-RP does not allow error for strings in the language and
RP does not allow error for strings not in the language. Hence, if a problem is in both
RP and
co-RP, then there must be no error for strings both in
and not in the language (i.e. no error whatsoever), which is exactly the definition of
ZPP. Important randomized space complexity classes include
BPL,
RL, and
RLP.
Interactive proof systems A number of complexity classes are defined using
interactive proof systems. Interactive proofs generalize the proofs definition of the complexity class
NP and yield insights into
cryptography,
approximation algorithms, and
formal verification. Interactive proof systems are
abstract machines that model computation as the exchange of messages between two parties: a prover P and a verifier V. The parties interact by exchanging messages, and an input string is accepted by the system if the verifier decides to accept the input on the basis of the messages it has received from the prover. The prover P has unlimited computational power while the verifier has bounded computational power (the standard definition of interactive proof systems defines the verifier to be polynomially-time bounded). The prover, however, is untrustworthy (this prevents all languages from being trivially recognized by the proof system by having the computationally unbounded prover solve for whether a string is in a language and then sending a trustworthy "YES" or "NO" to the verifier), so the verifier must conduct an "interrogation" of the prover by "asking it" successive rounds of questions, accepting only if it develops a high degree of confidence that the string is in the language.
Important complexity classes The class
NP is a simple proof system in which the verifier is restricted to being a deterministic polynomial-time
Turing machine and the procedure is restricted to one round (that is, the prover sends only a single, full proof—typically referred to as the
certificate—to the verifier). Put another way, in the definition of the class
NP (the set of decision problems for which the problem instances, when the answer is "YES", have proofs verifiable in polynomial time by a deterministic Turing machine) is a proof system in which the proof is constructed by an unmentioned prover and the deterministic Turing machine is the verifier. For this reason,
NP can also be called
dIP (deterministic interactive proof), though it is rarely referred to as such. It turns out that
NP captures the full power of interactive proof systems with deterministic (polynomial-time) verifiers because it can be shown that for any proof system with a deterministic verifier it is never necessary to need more than a single round of messaging between the prover and the verifier. Interactive proof systems that provide greater computational power over standard complexity classes thus require
probabilistic verifiers, which means that the verifier's questions to the prover are computed using
probabilistic algorithms. As noted in the section above on
randomized computation, probabilistic algorithms introduce error into the system, so complexity classes based on probabilistic proof systems are defined in terms of an error probability \epsilon. The most general complexity class arising out of this characterization is the class
IP (interactive polynomial time), which is the class of all problems solvable by an interactive proof system (P,V), where V is probabilistic polynomial-time and the proof system satisfies two properties: for a language L \in \mathsf{IP} • (Completeness) a string w in L implies \Pr[V \text{ accepts }w \text{ after interacting with } P] \ge \tfrac{2}{3} • (Soundness) a string w not in L implies \Pr[V \text{ accepts }w \text{ after interacting with } P] \le \tfrac{1}{3} An important feature of
IP is that it equals
PSPACE. In other words, any problem that can be solved by a polynomial-time interactive proof system can also be solved by a
deterministic Turing machine with polynomial space resources, and vice versa. A modification of the protocol for
IP produces another important complexity class:
AM (Arthur–Merlin protocol). In the definition of interactive proof systems used by
IP, the prover was not able to see the coins utilized by the verifier in its probabilistic computation—it was only able to see the messages that the verifier produced with these coins. For this reason, the coins are called
private random coins. The interactive proof system can be constrained so that the coins used by the verifier are
public random coins; that is, the prover is able to see the coins. Formally,
AM is defined as the class of languages with an interactive proof in which the verifier sends a random string to the prover, the prover responds with a message, and the verifier either accepts or rejects by applying a deterministic polynomial-time function to the message from the prover.
AM can be generalized to
AM[
k], where
k is the number of messages exchanged (so in the generalized form the standard
AM defined above is
AM[2]). However, it is the case that for all k \geq 2,
AM[
k]=
AM[2]. It is also the case that \mathsf{AM}[k]\subseteq\mathsf{IP}[k]. Other complexity classes defined using interactive proof systems include
MIP (multiprover interactive polynomial time) and
QIP (quantum interactive polynomial time).
Boolean circuits s, the \vee nodes are
OR gates, and the \neg nodes are
NOT gates. An alternative model of computation to the
Turing machine is the
Boolean circuit, a simplified model of the
digital circuits used in modern
computers. Not only does this model provide an intuitive connection between computation in theory and computation in practice, but it is also a natural model for
non-uniform computation (computation in which different input sizes within the same problem use different algorithms). Formally, a Boolean circuit C is a
directed acyclic graph in which edges represent wires (which carry the
bit values 0 and 1), the input bits are represented by source vertices (vertices with no incoming edges), and all non-source vertices represent
logic gates (generally the
AND,
OR, and
NOT gates). One logic gate is designated the output gate, and represents the end of the computation. The input/output behavior of a circuit C with n input variables is represented by the
Boolean function f_C:\{0,1\}^n \to \{0,1\}; for example, on input bits x_1,x_2,...,x_n, the output bit b of the circuit is represented mathematically as b = f_C(x_1,x_2,...,x_n). The circuit C is said to
compute the Boolean function f_C. Any particular circuit has a fixed number of input vertices, so it can only act on inputs of that size.
Languages (the formal representations of
decision problems), however, contain strings of differing lengths, so languages cannot be fully captured by a single circuit (this contrasts with the Turing machine model, in which a language is fully described by a single Turing machine that can act on any input size). A language is thus represented by a
circuit family. A circuit family is an infinite list of circuits (C_0,C_1,C_2,...), where C_n is a circuit with n input variables. A circuit family is said to decide a language L if, for every string w, w is in the language L if and only if C_n(w)=1, where n is the length of w. In other words, a string w of size n is in the language represented by the circuit family (C_0,C_1,C_2,...) if the circuit C_n (the circuit with the same number of input vertices as the number of bits in w) evaluates to 1 when w is its input. While complexity classes defined using Turing machines are described in terms of
time complexity,
circuit complexity classes are defined in terms of circuit size — the number of vertices in the circuit. The size complexity of a circuit family (C_0,C_1,C_2,...) is the function f:\mathbb{N} \to \mathbb{N}, where f(n) is the circuit size of C_n. The familiar function classes follow naturally from this; for example, a polynomial-size circuit family is one such that the function f is a
polynomial.
Important complexity classes The complexity class
P/poly is the set of languages that are decidable by polynomial-size circuit families. It turns out that there is a natural connection between circuit complexity and time complexity. Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in \mathsf{DTIME}(t(n)), where t is a function t:\mathbb{N} \to \mathbb{N}, then it has circuit complexity O(t^2(n)). It follows directly from this fact that
\mathsf{\color{Blue}P}\subset\textsf{P/poly}. In other words, any problem that can be solved in polynomial time by a deterministic Turing machine can also be solved by a polynomial-size circuit family. It is further the case that the inclusion is proper, i.e. \textsf{P}\subsetneq \textsf{P/poly} (for example, there are some
undecidable problems that are in
P/poly).
P/poly has a number of properties that make it highly useful in the study of the relationships between complexity classes. In particular, it is helpful in investigating problems related to
P versus NP. For example, if there is any language in
NP that is not in
P/poly, then \mathsf{P}\neq\mathsf{NP}.
P/poly is also helpful in investigating properties of the
polynomial hierarchy. For example, if
NP ⊆
P/poly, then
PH collapses to \Sigma_2^{\mathsf P}. A full description of the relations between
P/poly and other complexity classes is available at "
Importance of P/poly".
P/poly is also helpful in the general study of the properties of
Turing machines, as the class can be equivalently defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded
advice function. Two subclasses of
P/poly that have interesting properties in their own right are
NC and
AC. These classes are defined not only in terms of their circuit size but also in terms of their
depth. The depth of a circuit is the length of the longest
directed path from an input node to the output node. The class
NC is the set of languages that can be solved by circuit families that are restricted not only to having polynomial-size but also to having polylogarithmic depth. The class
AC is defined similarly to
NC, however gates are allowed to have unbounded fan-in (that is, the AND and OR gates can be applied to more than two bits).
NC is a notable class because it can be equivalently defined as the class of languages that have efficient
parallel algorithms.
Quantum computation The classes
BQP (bounded-error quantum polynomial time) and
QMA (Quantum Merlin Arthur), which are of key importance in
quantum information science, are defined using
quantum Turing machines. Their relationship is analogous to the relationship between
P and
NP, and also the relationship between
MA and
BPP. It is currently known that: :\mathsf{P \subseteq BPP \subseteq BQP\subseteq AWPP \subseteq PP \subseteq PSPACE\subseteq EXP} and: :\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE} though the relationship between
BQP and
NP remains unknown. ==Other types of problems==