3
$\begingroup$

Intro

I am trying to understand how those two models of interactive proof are different. I understand that

  • $\text{AM}$ relies on public coins (the prover knows the random bits used by the verifier)
  • $\text{IP}$ relies on private coins (the prover does not)

And here are some common results in those classes

  • Goldwasser and Sipser showed that if we allow a polynomial number of rounds $Q$, we have that $\text{IP}[Q] \subseteq \text{AM}[Q+2]$.

  • It has also been shown that if we allow a constant number of rounds $k$ in $\text{AM}$, we have that $\text{AM}[k] \subseteq \text{AM}[2]$

This seems to imply that if we limit $\text{IP}$ to a constant number of round $k$, we also have that $\text{IP}[k] \subseteq \text{AM}[k+2] \subseteq \text{AM}[2]$, and that these classes are very similar.


The thing that bugs me

But then, why do we have the huge difference that $\text{IP} = \text{PSPACE}$, while $\text{AM} \subseteq \prod_2^{\text{P}}$?

(see the Complexity Zoo on AM and IP)


Question(s)

  1. Why the difference? My assumption is that there is a convention to use $\text{AM}$ to speak about $\text{AM}[k]$, private coin, constant $k$ rounds protocols, and $\text{IP}$ to speak about $\text{IP}[\text{poly}]$ public coin, polynomial rounds protocols. Is it correct?

  2. Do the results holds if we swap the classes? $\text{IP}[k] \subseteq \prod_2^{\text{P}}$ does, but what about $\text{AM}[\text{poly}] = \text{PSPACE}$?

  3. As an additional question, we do know that a constant number of messages $k$ can be condensed into only two messages. Is there a similar result for a polynomial number of messages?

$\endgroup$
1
$\begingroup$

$AM$ is defined to be $AM[2]$, i.e. languages with 2-rounds Arthur-Merlin protocol, which is equal to $AM[k]$ for any constant $k$.

Two extra rounds are required to overcome the fact that the coins are public, i.e.

$IP[k]\subseteq AM[k+2]$ for any $k$ , constant or not, as stated in complexity zoo.

This means that $IP[poly]=AM[poly]=PSPACE$ (which answers your second question).

If $IP$ can be limited to a constant number of rounds (rather than polynomial), then we would have $PSPACE\subseteq IP[k]\subseteq \Pi^p_2$, and the hierarchy collapses to the second level, since $PH\subseteq PSPACE$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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