# Understanding MA protocol as a variant of TM for small space setting

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)$?

• (1) and (2) together imply that $\: L = \{\} \;$. $\;\;\;\;$ – user6973 Nov 23 '14 at 13:52
• 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 Nov 23 '14 at 14:22