7
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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) $\endgroup$
    – Nikhil
    Aug 26, 2019 at 4:25
  • $\begingroup$ 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? $\endgroup$
    – Clement C.
    Aug 26, 2019 at 4:42
  • $\begingroup$ 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. $\endgroup$
    – wrvb
    Aug 26, 2019 at 5:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Aug 26, 2019 at 7:29
  • 1
    $\begingroup$ 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? $\endgroup$
    – wrvb
    Aug 26, 2019 at 22:09

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – wrvb
    Aug 26, 2019 at 4:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Aug 26, 2019 at 9:07
  • 2
    $\begingroup$ @wrvb How do you check in $\exists\mathbb R$ that two points of a semialgebraic set belong to the same connected component? $\endgroup$
    – Emil Jeřábek
    Aug 26, 2019 at 9:11
  • 2
    $\begingroup$ Known algorithms make exponentially many queries. The introduction of this paper surveys the approach. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Aug 26, 2019 at 9:34
  • 2
    $\begingroup$ @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. $\endgroup$
    – wrvb
    Aug 26, 2019 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.