0
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ (1) and (2) together imply that $\: L = \{\} \;$. $\;\;\;\;$ $\endgroup$ – user6973 Nov 23 '14 at 13:52
  • 3
    $\begingroup$ 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$? $\endgroup$ – Emil Jeřábek Nov 23 '14 at 14:22

Your Answer

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

Browse other questions tagged or ask your own question.