Arthur-Merlin protocol

Question

I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$.

We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not formally defined $AMAMAMAM...AM$.

We did give a brief definition for it as a protocol, but i would like to see a formal definition without protocols, just like $AM$ and $MA$ (and $MAM$)

A definition for $AMA$ should suffice for me, just to get the hang of how it should look.

Thanks!

Answer 1

$AMA$ is basically a 3-round interactive proof system where the verifier (Arthur) is only allowed to send randomness to the prover (Merlin).
I haven't seen such an explicit definition yet, but I think we can formulate it as follows. The first round of AM[3] starts with Merlin sending a message $m_1$ to Arthur. In the second round, Arthur sends randomness $r$ to Merlin, which is followed by the final third round in which Merlin sends a message $m_2$. Arthur then decides to accept/reject using deterministic polynomial-time verifier $V$.

I think we can define the class as follows.
Definition: $L ∈ AMA$ if there exists a poly-time deterministic algorithm $V$ such that:

• If $x \in L \;(|x| = n)$ then $\exists P. Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 \right) \ge 2/3$ where $\; m_1 = P(x),\; m_2 = P(x, r)$
• If $x \notin L \;(|x| = n)$ then $\forall P. Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 \right) \le 1/3$ where $\; m_1 = P(x),\; m_2 = P(x, r)$

Note the prover $P$ is a function $P: \{0,1\}^* \rightarrow \{0,1\}^{q(n)}$, where $q(n)$ is a polynomial.

See: Computational Complxity by Arora-Barak's section 8.1.