11
$\begingroup$

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

$\endgroup$
  • 5
    $\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$ – Peter Shor Apr 24 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$ – Rupei Xu May 12 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.