exists a set of shifts of the random string s.t.at least one of them makes the machine to accept.) 3.Interaction Interactive proof system:NP plus interaction IP:Languages decidable by interactive proof system with polynomial-time Verifier. Theorem.IP PSPACE. (Proof idea:Some technique called algebraization...) A special type of interactive proof systems is one in which Verifier sends only public coins These are called AM[k],where k is the number of rounds.Let AM =Uk=1AM[k] Theorem.AM[k]AM[k+1]for any constant k.Thus AM AM[2]. (Proof idea:Switch the first two rounds,thus Verifier first sends public coins.If the original soundness error is small enough,then the switching maintains a decent soundness.) One can also define IP[k]as the languages decidable by k-round interactive proof systems. Theorem.IP[k]=AM[k +2].Thus all interactive proofs can be made public-coin. (Proof idea:The key tool is to efficiently certify the approximate size of a set.) One can also define one-round IP,which is the class MA.It's like NP but now Verifier is a BPP-machine (namely,Bounded-error,Polynomial-time and Probabilistic machine). Another important one-round IP is PCP[r(n),g(n)],in which Verifier uses at most r(n) random bits and at most g(n)queries to the proof. Theorem.PCP[O(log n),0(1)]=NP. The PCP theorems have direct implications in approximation algorithms(to show impossibility results)and many other connections to other areas in complexity theory. One can also consider more provers,who are allowed to discuss before seeing the input.We use MIP to denote the class of languages decidable by such multiple prover systems.exists a set of shifts of the random string s.t. at least one of them makes the machine to accept.) 3. Interaction Interactive proof system: NP plus interaction. IP: Languages decidable by interactive proof system with polynomial-time Verifier. Theorem. 𝐈𝐏 = 𝐏𝐒𝐏𝐀𝐂𝐄. (Proof idea: Some technique called algebraization…) A special type of interactive proof systems is one in which Verifier sends only public coins. These are called AM[k], where k is the number of rounds. Let 𝐀𝐌 = ⋃ 𝐀𝐌[𝑘] 𝑘≥1 . Theorem. 𝐀𝐌[𝑘] = 𝐀𝐌[𝑘 + 1] for any constant k. Thus 𝐀𝐌 = 𝐀𝐌[2]. (Proof idea: Switch the first two rounds, thus Verifier first sends public coins. If the original soundness error is small enough, then the switching maintains a decent soundness.) One can also define 𝐈𝐏[𝑘] as the languages decidable by k-round interactive proof systems. Theorem. 𝐈𝐏[𝑘] = 𝐀𝐌[𝑘 + 2]. Thus all interactive proofs can be made public-coin. (Proof idea: The key tool is to efficiently certify the approximate size of a set.) One can also define one-round IP, which is the class MA. It’s like NP but now Verifier is a BPP-machine (namely, Bounded-error, Polynomial-time and Probabilistic machine). Another important one-round IP is 𝐏𝐂𝐏[𝑟(𝑛),𝑞(𝑛)], in which Verifier uses at most 𝑟(𝑛) random bits and at most 𝑞(𝑛) queries to the proof. Theorem. 𝐏𝐂𝐏[𝑂(log 𝑛), 𝑂(1)] = 𝐍𝐏. The PCP theorems have direct implications in approximation algorithms (to show impossibility results) and many other connections to other areas in complexity theory. One can also consider more provers, who are allowed to discuss before seeing the input. We use MIP to denote the class of languages decidable by such multiple prover systems