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 contained in PSPACE and to contain NP. See this paper for a reference; as far as I can tell, that's the paper that introduced $$\exists\mathbb{R}$$ as a distinct complexity class.

However, Reif gives an explicit construction which takes a Turing machine with a polynomial space bound and a string, and constructs a motion planning instance which has a solution if and only if the machine accepts the string. Since motion plan existence can be reduced to $$\exists\mathbb{R}$$ (see, e.g., this paper by Schwartz and Sharir), this seems to imply that $$\mathbf{PSPACE} \subseteq \exists\mathbb{R}$$, and thus that $$\mathbf{PSPACE} = \exists\mathbb{R}$$.

I don't come from a CS theory background, and I feel like I must be missing something fundamental, because there looks to be a whole subfield of authors writing papers placing various problems in $$\exists\mathbb{R}$$.

• I think this is highly unlikely. PSPACE is closed under complement,and I don't think $\exists R$ is expected to be (though I don't know of any strong consequence of this) Aug 26 '19 at 4:25
• I don't quite understand the proposed reduction. Say, you have a decision problem $P\in \mathbf{PSPACE}$. How do you map it to a problem in $\exists\mathbb{R}$? Here, you seem to suggest there is a reduction for the problem "On input $M,x$ s.t. $M$ only uses polynomial space, does $M$ accept $x$?" So given some problem $P$ as above, you get a machine $M_P$ with a polynomial space bound, and then on input $x$ you run the reduction (call it $\phi$) on $(M_P,x)$ to generate an instance of some problem in $\exists \mathbb{R}$ (right?). What is the complexity of executing $\phi$ to do that? Aug 26 '19 at 4:42
• Reif's construction takes in an input string $w$ of length $n$ and a Turing machine $T$ guaranteed to terminate using only $p(n)$ space, and uses $\log(n)$ work space to spit out a description of a semialgebraic set using $\mathrm{poly}(p(n))$ linear inequalities and polynomial equations and two points on the set $x_1$ and $x_2$ such that $x_1$ and $x_2$ lie on the same connected component of the set if and only if $T$ accepts $w$. So if I understand your question and Reif's paper and computational complexity (lots of ifs!) since $\phi$ uses log space it must be ptime.
– wrvb
Aug 26 '19 at 5:18
• I do not see any evidence that motion planning can be reduced to $\exists\mathbb{R}$. The paper by Schwartz and Sharir does not claim that either. Aug 26 '19 at 7:29
• The combination of Bjørn Kjos-Hanssen's answer with Emil Jeřábek and Kristoffer Arnsfelt Hansen's comments seems to answer my question. Is it appropriate to accept Bjørn's answer in this situation?
– wrvb
Aug 26 '19 at 22:09

The issue may be whether or not Schwartz and Sharir show that motion plan existence is many-one polynomial time reducible to $$\exists\mathbb R$$.

If they need several queries to $$\exists\mathbb R$$ for a given motion plan existence instance, then that's not a many-one reduction.

• If I understand the terminology correctly, that is not the case---Schwartz and Sharir showed that motion planning is equivalent to checking if two points lie on the same connected component of a semialgebraic set. At the time, there were no polynomial space algorithms known for deciding such queries; the first such algorithm was given by Canny in or around 1987.
– wrvb
Aug 26 '19 at 4:14
• Even with Turing reductions, $\mathrm{PSPACE=P^{\exists\mathbb R}}$ would still be a breakthrough (and completely unexpected) result. The only known lower bound on $\exists\mathbb R$ is NP. Aug 26 '19 at 9:07
• @wrvb How do you check in $\exists\mathbb R$ that two points of a semialgebraic set belong to the same connected component? Aug 26 '19 at 9:11
• Known algorithms make exponentially many queries. The introduction of this paper surveys the approach. Aug 26 '19 at 9:34
• @KristofferArnsfeltHansen, I think that paper is what I was missing. I was (mistakenly) assuming that $\exists\mathbb{R}$ implied an algorithm for checking if two points are on the same connected component, since we could just query whether there exist parameters of a polynomial that remains inside a single connected component. But as that paper points out, the path need not be a low-degree polynomial, so that doesn't actually give a reduction.
– wrvb
Aug 26 '19 at 22:04