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$?
11
$\begingroup$
$\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
