<p>The issue may be whether or not Schwartz and Sharir show that motion plan existence is <strong>many-one</strong> polynomial time reducible to <span class="math-container">$\exists\mathbb R$</span>.</p>

<p>If they need several queries to <span class="math-container">$\exists\mathbb R$</span> for a given motion plan existence instance, then that's not a many-one reduction.</p>

CC BY-SA 4.0
2019-08-26T04:14:23.067Z
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
CC BY-SA 4.0
2019-08-26T09:07:09.317Z
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.
Emil Jeřábek
CC BY-SA 4.0
2019-08-26T09:11:56.173Z
@wrvb How do you check in $\exists\mathbb R$ that two points of a semialgebraic set belong to the same connected component?
Emil Jeřábek
CC BY-SA 4.0
2019-08-26T09:34:54.380Z
Known algorithms make exponentially many queries. The introduction of [this paper](https://arxiv.org/abs/1201.6439) surveys the approach.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-08-26T22:04:45.723Z
@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
CC BY-SA 4.0
2019-08-26T03:52:39.510Z
2019-08-26T03:52:39.510Z
Bjørn Kjos-Hanssen
<p>The complexity class <span class="math-container">$\exists \mathbb{R}$</span> (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 <a href="http://ovid.cs.depaul.edu/documents/convex.pdf" rel="noreferrer">this paper</a> for a reference; as far as I can tell, that's the paper that introduced <span class="math-container">$\exists\mathbb{R}$</span> as a distinct complexity class.</p>

<p>However, <a href="https://doi.org/10.1109/SFCS.1979.10" rel="noreferrer">Reif</a> 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 <span class="math-container">$\exists\mathbb{R}$</span> (see, e.g., <a href="https://www.sciencedirect.com/science/article/pii/0196885883900143" rel="noreferrer">this paper</a> by Schwartz and Sharir), this seems to imply that <span class="math-container">$\mathbf{PSPACE} \subseteq \exists\mathbb{R}$</span>, and thus that <span class="math-container">$\mathbf{PSPACE} = \exists\mathbb{R}$</span>.</p>

<p>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 <span class="math-container">$\exists\mathbb{R}$</span>.</p>

CC BY-SA 4.0
2019-08-26T04:25:15.733Z
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)
Nikhil
CC BY-SA 4.0
2019-08-26T04:42:03.220Z
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?
Clement C.
CC BY-SA 4.0
2019-08-26T05:18:31.637Z
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
CC BY-SA 4.0
2019-08-26T07:29:03.457Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-08-26T22:09:47.107Z
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
<pspace><existential-theory-of-the-reals>
Does $\exists\mathbb{R}=\mathbf{PSPACE}$?
wrvb
# Does $\exists\mathbb{R}=\mathbf{PSPACE}$?

(Asked by: username_0 on 2019-08-26)

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](http://ovid.cs.depaul.edu/documents/convex.pdf) 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](https://doi.org/10.1109/SFCS.1979.10) 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](https://www.sciencedirect.com/science/article/pii/0196885883900143) 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}$.

**Tags:** pspace, existential-theory-of-the-reals
> **Comments:**
> **username_1**: 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)  
> **username_2**: 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?  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_4 on 2019-08-26. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: 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.  
> **username_5**: @wrvb How do you check in $\exists\mathbb R$ that two points of a semialgebraic set belong to the same connected component?  
> **username_3**: Known algorithms make exponentially many queries. The introduction of [this paper](https://arxiv.org/abs/1201.6439) surveys the approach.  
> **username_0**: @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.  

---

