# Randomized Version of NP

I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $$\text{IP}, \text{BPP}, \text{RP}$$, etc.

Since the above classes are well-known, I will give a hand-wavy definition of $$\text{IP}$$. Then, I will state my question. Roughly speaking, a language $$L \in \text{IP}$$ iff there exist a pair of interactive algorithms Prover $$P$$ and Verifier $$V$$, with $$V$$ running in probabilistic polynomial time (in the length of the input $$x$$: $$x$$ is common to both $$P$$ and $$V$$), such that:

• If $$x\in L$$, and the Prover $$P$$ follows the protocol, then the probability that the Verifier $$V$$ accepts is 1, and
• if $$x\notin L$$, then for any Prover $$P$$ (even a cheating one), the probability that the Verifier $$V$$ accepts is at most $$\frac{1}{2}$$.

I note that $$P$$ is allowed to be computationally unbounded.

Now to understand the power of interaction, I started to see what happens when restrict or give up the interaction between the prover and the verifier. I read the following in this lecture here, given by Jonathan Katz:

1- Assume that the verifier has input $$x$$. If the protocol is such that the prover $$P$$ sends a proof $$\pi$$ (to the fact that $$x\in L$$) to the verifier $$V$$, and then the interaction ends. The verifier has then to verify that $$x \in L$$, given $$\pi$$. If the verifier is deterministic and runs in polynomial time in $$|x|$$. Then, it is not hard to see that such interactive protocol is equivalent to the complexity class $$\text{NP}$$.

2- Now if we consider the interaction protocol in item 1, and additionally allow the verifier to be probabilistic, then we get more than $$\text{NP}$$. Specifically, it is known that in this case, any language in $$L \in \text{BPP}$$ can be handled by the protocol. Note that this actually suggest that we can eliminate the error when $$x\in L$$.

The protocol in item 2, can be thought of as a randomized version of $$\text{NP}$$.

Here comes my question: can the protocol given in item 2, handle any language in $$\text{IP}$$? That is, given a language $$L\in \text{IP}$$, can we give up the interaction entirely and still be able to verify that $$x \in L$$ in probabilistic polynomial time with completeness $$1$$, and soundness at most $$\frac{1}{2}$$? Intuitively, I think the answer is unknown because randomized complexity classes are conjectured to be contained in $$\text{P}$$ and we don't even know whether $$\text{P}$$ is a strict subset of $$\text{PSPACE} = \text{IP}$$.

• Obviously there is no definite answer, since we don't know whether NP=PSPACE, and we do know that IP=PSPACE, but I think what you're alluding to is the Arthur-Merlin hierarchy. See here: cs.stackexchange.com/questions/57475/…). Mar 21, 2021 at 13:01
• Also, you can always get rid of a constant number of rounds without sacrificing completeness (simply by having the verifier guess ahead what the answer will be, and ask questions accordingly), but you cannot eliminate a polynomial number of rounds this way. Mar 21, 2021 at 13:06
• Thanks for the reference, I see your point. This indeed answers my question. Mar 21, 2021 at 14:42

Since $$BPP\subseteq \Sigma_2\cap \Pi_2$$ it immediately follows that $$MA\subseteq \Sigma_2\cap \Pi_2$$, which is believed to be a strict subset of PSPACE which contains the entire polynomial hierarchy.
• This is the class $PCP[q(n),r(n)]$, see zoo. With $q,r$ polynomial in $n$ the class is actually NEXP. For a simple example on how a longer proof might be able to assist you, consider GNI, with the membership proof for input $(G_1,G_2)\in GNI$ being a string $\pi$ index by all possible $n$ vertex graphs such that $\pi_G=1$ iff $G$ is isomorphic to $G_1$ and not to $G_2$. The verifier will toss a coin $b$ a query the proof on a random permutation of $G_b$. Mar 21, 2021 at 14:51