<p>MA protocol is one of the most basic models of interactive proofs. </p>

<p>Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier  who verifies if $w$ is a positive witness of $x$ using  random bits $r$.  We say that $L$ is decided by MA protocol $\mathcal{P}$, if the following two conditions hold. </p>

<ol>
<li>$x\in L\Rightarrow \exists w\,\Pr_r[\mathcal{P}(x,w,r)=1]&gt;2/3$, </li>
<li>$x\notin L\Rightarrow \forall w\,\Pr_r[\mathcal{P}(x,w,r)=1]&lt;1/3$.</li>
</ol>

<blockquote>
  <p>My question is:  What is the formal description of Turing Machine exactly simulating MA protocol with space $S(n)$? </p>
</blockquote>

CC BY-SA 3.0
2014-11-23T14:22:06.393Z
I don’t really understand the question. Do you want to ask what class we get from MA if we further impose a space restriction? And anyway, what *is* the space of the protocol? Is it the space used by Arthur’s computation? Does it include $w$? Does it include $r$?
Emil Jeřábek
<cc.complexity-theory><complexity-classes><interactive-proofs><machine-models>
Understanding MA protocol as a variant of TM for small space setting
huna
# Understanding MA protocol as a variant of TM for small space setting

(Asked by: username_0 on 2014-11-23)

MA protocol is one of the most basic models of interactive proofs.

Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive witness of $x$ using random bits $r$. We say that $L$ is decided by MA protocol $\mathcal{P}$, if the following two conditions hold.

1. $x\in L\Rightarrow \exists w\,\Pr\_r[\mathcal{P}(x,w,r)=1]>2/3$,
2. $x\notin L\Rightarrow \forall w\,\Pr\_r[\mathcal{P}(x,w,r)=1]<1/3$.

> My question is: What is the formal description of Turing Machine exactly simulating MA protocol with space $S(n)$?

**Tags:** cc.complexity-theory, complexity-classes, interactive-proofs, machine-models

> **Comments:**
> **username_1**: I don’t really understand the question. Do you want to ask what class we get from MA if we further impose a space restriction? And anyway, what *is* the space of the protocol? Is it the space used by Arthur’s computation? Does it include $w$? Does it include $r$?  

---

## 0 answers

