Editing Complexity class (section)

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