I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such that whenever $x \in L$, $\Pr[V(x,\pi,r)\text{ accepts}]$ is exponentially high and is exponentially low otherwise. Like in the proof of $BPP \in \Sigma_2$, there are relatively few bitvectors $z_1, \cdots z_l$ such that translating the set of "good" random bits with them cover the entire space of such bits. The perfectly complete protocol also requires the prover to provide these strings.

I have seen various sources casually mentioning that any AM protocol can be modified to achieve perfect completeness. How can this be achieved?

Can this also be done for IP?

  • 1
    $\begingroup$ Here is the very first link for "am perfect completeness": cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture17.pdf. Try to be more resourceful. $\endgroup$ – Yuval Filmus Mar 23 at 13:24
  • $\begingroup$ Thank you for the link but I have already seen this. I do not really understand how they convert MAM protocols to AM protocols. I have also tried reading the other links and there are always some small details which evade me. So I would appreciate a more complete answer. $\endgroup$ – Agnishom Chattopadhyay Mar 23 at 14:11
  • $\begingroup$ The proof of MAM=AM is sketched in the preceding lecture, cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture1516.pdf. You can also find it in other online resources. $\endgroup$ – Yuval Filmus Mar 23 at 16:57
  • $\begingroup$ If there are resources you've already found that look relevant but don't quite answer your question, it is good practice to describe them in your question, summarize them, and explain in what way they don't meet your needs. Show your research -- that makes your question more helpful for others, and reduces people giving you suggestions you were already aware of (wasting your time and theirs). $\endgroup$ – D.W. Mar 23 at 18:03

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.