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$?
$\begingroup$
$\endgroup$
2
-
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$– Peter ShorApr 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$– user17918May 12, 2019 at 11:40
Add a comment
|