Editing Complexity class (section)

==Other models of computation==
While deterministic and non-deterministic [[Turing machine]]s 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 machine]]s, including the classes '''[[Bounded-error probabilistic polynomial|BPP]]''', '''[[PP (complexity)|PP]]''', '''[[RP (complexity)|RP]]''', and '''[[ZPP (complexity)|ZPP]]'''
* A number of classes are defined using [[interactive proof system]]s, including the classes '''[[IP (complexity)|IP]]''', '''[[MA (complexity)|MA]]''', and '''[[AM (complexity)|AM]]'''
* A number of classes are defined using [[Boolean circuit]]s, including the classes '''[[P/poly]]''' and its subclasses '''[[NC (complexity)|NC]]''' and '''[[AC (complexity)|AC]]'''
* A number of classes are defined using [[quantum Turing machine]]s, including the classes '''[[BQP]]''' and '''[[QMA]]'''

These are explained in greater detail below.

===Randomized computation===
{{Main|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 algorithm]]s.

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 <math>\epsilon</math>. A probabilistic Turing machine <math>M</math> is said to recognize a language <math>L</math> with error probability <math>\epsilon</math> if:
# a string <math>w</math> in <math>L</math> implies that <math>\text{Pr}[M \text{ accepts } w] \geq 1 - \epsilon</math>
# a string <math>w</math> not in <math>L</math> implies that <math>\text{Pr}[M \text{ rejects } w] \geq 1 - \epsilon</math>

====Important complexity classes====
[[File:Randomized Complexity Classes.svg|thumb|The relationships between the fundamental probabilistic complexity classes. BQP is a probabilistic [[Quantum complexity theory|quantum complexity]] class and is described in the quantum computing section.]]

The fundamental randomized time complexity classes are '''[[ZPP (complexity)|ZPP]]''', '''[[RP (complexity)|RP]]''', '''[[co-RP]]''', '''[[BPP (complexity)|BPP]]''', and '''[[PP (complexity)|PP]]'''.

The strictest class is '''[[ZPP (complexity)|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 (complexity)|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 <math>M</math> such that if a string is not in the language then <math>M</math> always rejects and if a string is in the language then <math>M</math> 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 (complexity)|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 algorithm]]s that can be run quickly on real computers. '''BPP''' is also at the center of the important unsolved problem in computer science over whether '''[[BPP (complexity)#Problems|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 (complexity)|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: <math>\textsf{ZPP}=\textsf{RP}\cap\textsf{co-RP}</math>. 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 (complexity)|BPL]]''', '''[[RL (complexity)|RL]]''', and '''[[Randomized Logarithmic-space Polynomial-time|RLP]]'''.

===Interactive proof systems===
{{Main|Interactive proof system}}
A number of complexity classes are defined using '''[[interactive proof systems]]'''. Interactive proofs generalize the proofs definition of the complexity class '''[[NP (complexity)|NP]]''' and yield insights into [[cryptography]], [[approximation algorithm]]s, and [[formal verification]].

[[File:Interactive proof (complexity).svg|thumb|300px|General representation of an interactive proof protocol]]
Interactive proof systems are [[abstract machine]]s that model computation as the exchange of messages between two parties: a prover <math>P</math> and a verifier <math>V</math>. 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 <math>P</math> 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.{{sfn|Arora|Barak|2009|p=144}}

====Important complexity classes====
The class '''[[NP (complexity)|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 (complexity)|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 algorithm]]s. 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 <math>\epsilon</math>. 

The most general complexity class arising out of this characterization is the class '''[[IP (complexity)|IP]]''' (interactive polynomial time), which is the class of all problems solvable by an interactive proof system <math>(P,V)</math>, where <math>V</math> is probabilistic polynomial-time and the proof system satisfies two properties: for a language <math>L \in \mathsf{IP}</math>
# (Completeness) a string <math>w</math> in <math>L</math> implies <math>\Pr[V \text{ accepts }w \text{ after interacting with } P] \ge \tfrac{2}{3}</math>
# (Soundness) a string <math>w</math> not in <math>L</math> implies <math>\Pr[V \text{ accepts }w \text{ after interacting with } P] \le \tfrac{1}{3}</math>

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 (complexity)|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 <math>k \geq 2</math>, '''AM'''[''k'']='''AM'''[2]. It is also the case that <math>\mathsf{AM}[k]\subseteq\mathsf{IP}[k]</math>.

Other complexity classes defined using interactive proof systems include '''[[Interactive proof system#MIP|MIP]]''' (multiprover interactive polynomial time) and '''[[QIP (complexity)|QIP]]''' (quantum interactive polynomial time).

===Boolean circuits===
{{Main|Circuit complexity}}
[[File:Three input boolean circuit.svg|thumb|right|350px|Example Boolean circuit computing the Boolean function <math>f_C(x_1,x_2,x_3)=\neg (x_1 \wedge x_2) \wedge ((x_2 \wedge x_3) \vee \neg x_3)</math>, with example input <math>x_1=0</math>, <math>x_2=1</math>, and <math>x_3=0</math>. The <math>\wedge</math> nodes are [[AND gate]]s, the <math>\vee</math> nodes are [[OR gate]]s, and the <math>\neg</math> nodes are [[NOT gate]]s.]]
An alternative model of computation to the [[Turing machine]] is the '''[[Boolean circuit]]''', a simplified model of the [[digital circuit]]s used in modern [[computer]]s. 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 <math>C</math> 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 gate]]s (generally the [[AND gate|AND]], [[OR gate|OR]], and [[NOT gate]]s). One logic gate is designated the output gate, and represents the end of the computation. The input/output behavior of a circuit <math>C</math> with <math>n</math> input variables is represented by the [[Boolean function]] <math>f_C:\{0,1\}^n \to \{0,1\}</math>; for example, on input bits <math>x_1,x_2,...,x_n</math>, the output bit <math>b</math> of the circuit is represented mathematically as <math>b = f_C(x_1,x_2,...,x_n)</math>. The circuit <math>C</math> is said to ''compute'' the Boolean function <math>f_C</math>.

Any particular circuit has a fixed number of input vertices, so it can only act on inputs of that size. [[Formal language|Languages]] (the formal representations of [[decision problem]]s), 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 <math>(C_0,C_1,C_2,...)</math>, where <math>C_n</math> is a circuit with <math>n</math> input variables. A circuit family is said to decide a language <math>L</math> if, for every string <math>w</math>, <math>w</math> is in the language <math>L</math> if and only if <math>C_n(w)=1</math>, where <math>n</math> is the length of <math>w</math>. In other words, a string <math>w</math> of size <math>n</math> is in the language represented by the circuit family <math>(C_0,C_1,C_2,...)</math> if the circuit <math>C_n</math> (the circuit with the same number of input vertices as the number of bits in <math>w</math>) evaluates to 1 when <math>w</math> 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 <math>(C_0,C_1,C_2,...)</math> is the function <math>f:\mathbb{N} \to \mathbb{N}</math>, where <math>f(n)</math> is the circuit size of <math>C_n</math>. The familiar function classes follow naturally from this; for example, a polynomial-size circuit family is one such that the function <math>f</math> 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 <math>\mathsf{DTIME}(t(n))</math>, where <math>t</math> is a function <math>t:\mathbb{N} \to \mathbb{N}</math>, then it has circuit complexity <math>O(t^2(n))</math>.{{sfn|Sipser|2006|p=355}} It follows directly from this fact that [[P (complexity)|<math>\mathsf{\color{Blue}P}\subset\textsf{P/poly}</math>]]. 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. <math>\textsf{P}\subsetneq \textsf{P/poly}</math> (for example, there are some [[undecidable problem]]s 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|'''P''' versus '''NP''']]. For example, if there is any language in '''NP''' that is not in '''P/poly''', then <math>\mathsf{P}\neq\mathsf{NP}</math>.{{sfn|Arora|Barak|2009|p=286}} '''P/poly''' is also helpful in investigating properties of the [[polynomial hierarchy]]. For example, if '''[[NP (complexity)|NP]]''' ⊆ '''P/poly''', then '''PH''' collapses to <math>\Sigma_2^{\mathsf P}</math>. A full description of the relations between '''P/poly''' and other complexity classes is available at "[[P/poly#Importance of P/poly|Importance of P/poly]]". '''P/poly''' is also helpful in the general study of the properties of [[Turing machine]]s, as the class can be equivalently defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded [[advice (complexity)|advice function]].

Two subclasses of '''P/poly''' that have interesting properties in their own right are '''[[NC (complexity)|NC]]''' and '''[[AC (complexity)|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 algorithm]]s.

===Quantum computation===
{{expand section|date=April 2017}}

The classes '''[[BQP]]''' and '''[[QMA]]''', which are of key importance in [[quantum information science]], are defined using '''[[quantum Turing machine]]s'''.