2
$\begingroup$

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}$.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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/…). $\endgroup$
    – Shaull
    Commented Mar 21, 2021 at 13:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Shaull
    Commented Mar 21, 2021 at 13:06
  • $\begingroup$ Thanks for the reference, I see your point. This indeed answers my question. $\endgroup$
    – Bader Abu Radi
    Commented Mar 21, 2021 at 14:42

1 Answer 1

Reset to default
3
$\begingroup$

The class you described is MA (interactive proofs consisting of one round where the prover, Merlin, sends one meassage to the verifier, Arthur, which then has to decide in probabilistic polynomial time whether to accept or reject).

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the reference. For curiosity, do you think the following gives an advantage to Arthur? What if we allow Merlin to send an arbitrarily long proof (say exponential-size proof) and assume that Arthur can get to any cell in constant time? That is, instead of moving the head of the machine to cell number k, which takes k steps, we can access the k'th cell in constant time. Perhaps with this ability, the long proof that Arthur gets can help him more even if his runtime is still polynomial. $\endgroup$
    – Bader Abu Radi
    Commented Mar 21, 2021 at 14:45
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Ariel
    Commented Mar 21, 2021 at 14:51
  • $\begingroup$ Many thanks, I will read about the PCP class, and the example is very clear. $\endgroup$
    – Bader Abu Radi
    Commented Mar 21, 2021 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.