i think that it's true that AM is contained in $\Pi_2$ but I'm not sure how to prove it. How do I prove that $AM \subseteq \Pi_2$?

  • 2
    $\begingroup$ 1. What have you tried? What approaches have you tried, for trying to prove this? Where did you get stuck? Why do you think it's true? What research have you done? 2. You can use LaTeX for mathematics. $\endgroup$ – D.W. Jan 16 '16 at 17:41
  • $\begingroup$ This is proved in the same way as for BPP (also contained in $\Pi_2$). Both are standard results that can be found in textbooks and online lecture notes, and even Wikipedia. $\endgroup$ – Yuval Filmus Jan 16 '16 at 18:11
  • $\begingroup$ @YuvalFilmus : ​ ​ ​ That depends on one's initial definition of AM. ​ If private coins are allowed, then approximate counting is needed. ​ Allowing any constant number of rounds makes things still harder, though not by as much. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Jan 16 '16 at 19:14
  • $\begingroup$ @Ricky Demer The definition we used is with public coins. And I am having a hard time proving that. Can use some help $\endgroup$ – scifie Jan 17 '16 at 6:56
  • $\begingroup$ Does your definition allow any constant number of rounds, or restrict to [verifier sends random coins, prover sends response, verifier gives output]? ​ If the later, does your definition let the verifier use more random coins in its last phase? ​ ​ ​ ​ $\endgroup$ – user12859 Jan 17 '16 at 14:14

Your Answer


Browse other questions tagged or ask your own question.