Questions tagged [existential-theory-of-the-reals]

Filter by
Sorted by
Tagged with
8
votes
0answers
205 views

Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$

As pointed out explicitly by Emil Jeřábek here: Even with Turing reductions, $\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$ would still be a breakthrough (and completely unexpected) result. So ...
7
votes
1answer
252 views

Does $\exists\mathbb{R}=\mathbf{PSPACE}$?

The complexity class $\exists \mathbb{R}$ (the existential theory of the reals, i.e. problems that can be reduced to deciding if a collection of polynomial inequalities has a solution) is known to be ...
11
votes
0answers
163 views

$\exists \mathbb R$ and IP

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 ...