We know NP$\subseteq$ $\exists \mathbb R$$\subseteq$ PSPACE=IP, but is there some more direct proof for $\exists \mathbb R\subseteq$ IP?

What about the other direction, are there some Arthur-Merlin games that are in $\exists \mathbb R$?

  • 6
    $\begingroup$ Given how complicated the $\exists \mathbb{R} \subseteq \mathrm{PSPACE}$ is, a more direct proof of $\exists \mathbb{R} \subseteq \mathrm{IP}$ would be a major result. I can't find such a proof with Google. $\endgroup$ Apr 24, 2019 at 12:08
  • $\begingroup$ The art gallery problem is $\exists\mathbb{R}$-complete arxiv.org/pdf/1704.06969.pdf I wonder whether your question can be answered if one can design some Arthur-Merlin games for the art gallery problem. $\endgroup$
    – user17918
    May 12, 2019 at 11:40


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.