<p>As pointed out explicitly by Emil Jeřábek <a href="https://cstheory.stackexchange.com/questions/44446/does-exists-mathbbr-mathbfpspace#comment100974_44447">here</a>:</p>

<blockquote>
  <p>Even with Turing reductions, <span class="math-container">$\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$</span> would still be a breakthrough (and completely unexpected) result.</p>
</blockquote>

<p>So the expectation is that <span class="math-container">$\exists\mathbb{R}$</span> (<a href="https://en.m.wikipedia.org/wiki/Existential_theory_of_the_reals" rel="noreferrer">existential theory of reals</a>) is significantly easier than <span class="math-container">$\mathbf{PSPACE}$</span>.</p>

<p>It is nice to have some expectation, but are there conditional separations of <span class="math-container">$\exists\mathbb{R}$</span>, <span class="math-container">$\exists\mathbb{R}\cup\mathbb{co}\exists\mathbb{R}$</span> or <span class="math-container">$\mathbf{P}^{\exists\mathbb{R}}$</span> from <span class="math-container">$\mathbf{PSPACE}$</span> that can actually be achieved to justify those expectations?</p>

<hr>

<p>Let us conditionally assume that the counting hierarchy would count as significantly easier than <span class="math-container">$\mathbf{PSPACE}$</span>. <a href="https://www.scottaaronson.com/blog/?p=4301#comment-1818917" rel="noreferrer">Here</a> Scott Aaronson vaguely remembers:</p>

<blockquote>
  <p>indeed it’s in the counting hierarchy I think</p>
</blockquote>

<p>Is his vague recollection correct? Is there at least some paper which could explain where those vague recollections came from, even if it doesn't directly prove this?</p>

<hr>

<p><a href="https://cstheory.stackexchange.com/questions/44446/does-exists-mathbbr-mathbfpspace#comment100966_44446">Here</a> is another argument why <span class="math-container">$\exists\mathbb{R}$</span> should be significantly easier than <span class="math-container">$\mathbf{PSPACE}$</span>: </p>

<blockquote>
  <p>I think this is highly unlikely. <span class="math-container">$\mathbf{PSPACE}$</span> is closed under complement,and I don't think <span class="math-container">$\exists\mathbb{R}$</span> is expected to be (though I don't know of any strong consequence of this)</p>
</blockquote>

<p>If we conditionally assume that <span class="math-container">$\exists\mathbb{R}$</span> is not closed under complement, how significant could we separate it from <span class="math-container">$\mathbf{PSPACE}$</span> then? Can we at least separate <span class="math-container">$\exists\mathbb{R}\cup\mathbb{co}\exists\mathbb{R}$</span> from <span class="math-container">$\mathbf{PSPACE}$</span>?</p>

CC BY-SA 4.0
2019-09-18T17:37:37.177Z
For the record: I had an answer but it was just a brain fart. I have deleted it
Ryan Williams
CC BY-SA 4.0
2019-09-18T20:40:03.893Z
@RyanWilliams Who knows, maybe that [Allender-Burgisser-Kjeldgaard-Pedersen-Bro Miltersen, "On the complexity of numerical analysis"](https://epubs.siam.org/doi/10.1137/070697926) ([Google Scholar link](https://scholar.google.com/scholar?cluster=13110608121785405677&hl=en&as_sdt=40000005&sciodt=0,22)) paper could still explain where those vague recollections came from. (I had edited the question accordingly before you deleted your answer, to make it clear that your answer might indeed address that part.)
Thomas Klimpel
CC BY-SA 4.0
2019-09-18T21:32:33.783Z
That's likely where Scott got this idea. I was just confused and overly optimistic :)
Ryan Williams
CC BY-SA 4.0
2019-09-19T08:20:29.933Z
$\exists\mathbb{R}$ is not known to be in the counting hierarchy, but I believe that it is not unlikely that it actually is.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-09-19T18:00:03.193Z
@KristofferArnsfeltHansen: Does that mean you believe that it likely actually is?
user21820
CC BY-SA 4.0
2019-09-20T09:23:23.113Z
@user21820: I'm maybe 50/50 on that one.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><pspace><existential-theory-of-the-reals>
Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$
Thomas Klimpel
# Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$

(Asked by: username_0 on 2019-09-17)

As pointed out explicitly by Emil Jeřábek [here](https://cstheory.stackexchange.com/questions/44446/does-exists-mathbbr-mathbfpspace#comment100974_44447):

> Even with Turing reductions, $\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$ would still be a breakthrough (and completely unexpected) result.

So the expectation is that $\exists\mathbb{R}$ ([existential theory of reals](https://en.m.wikipedia.org/wiki/Existential_theory_of_the_reals)) is significantly easier than $\mathbf{PSPACE}$.

It is nice to have some expectation, but are there conditional separations of $\exists\mathbb{R}$, $\exists\mathbb{R}\cup\mathbb{co}\exists\mathbb{R}$ or $\mathbf{P}^{\exists\mathbb{R}}$ from $\mathbf{PSPACE}$ that can actually be achieved to justify those expectations?

---

Let us conditionally assume that the counting hierarchy would count as significantly easier than $\mathbf{PSPACE}$. [Here](https://www.scottaaronson.com/blog/?p=4301#comment-1818917) Scott Aaronson vaguely remembers:

> indeed it’s in the counting hierarchy I think

Is his vague recollection correct? Is there at least some paper which could explain where those vague recollections came from, even if it doesn't directly prove this?

---

[Here](https://cstheory.stackexchange.com/questions/44446/does-exists-mathbbr-mathbfpspace#comment100966_44446) is another argument why $\exists\mathbb{R}$ should be significantly easier than $\mathbf{PSPACE}$:

> I think this is highly unlikely. $\mathbf{PSPACE}$ is closed under complement,and I don't think $\exists\mathbb{R}$ is expected to be (though I don't know of any strong consequence of this)

If we conditionally assume that $\exists\mathbb{R}$ is not closed under complement, how significant could we separate it from $\mathbf{PSPACE}$ then? Can we at least separate $\exists\mathbb{R}\cup\mathbb{co}\exists\mathbb{R}$ from $\mathbf{PSPACE}$?

**Tags:** cc.complexity-theory, pspace, existential-theory-of-the-reals

> **Comments:**
> **username_1**: For the record: I had an answer but it was just a brain fart. I have deleted it  
> **username_0**: @RyanWilliams Who knows, maybe that [Allender-Burgisser-Kjeldgaard-Pedersen-Bro Miltersen, "On the complexity of numerical analysis"](https://epubs.siam.org/doi/10.1137/070697926) ([Google Scholar link](https://scholar.google.com/scholar?cluster=13110608121785405677&hl=en&as_sdt=40000005&sciodt=0,22)) paper could still explain where those vague recollections came from. (I had edited the question accordingly before you deleted your answer, to make it clear that your answer might indeed address that part.)  
> **username_1**: That's likely where Scott got this idea. I was just confused and overly optimistic :)  
> **username_2**: $\exists\mathbb{R}$ is not known to be in the counting hierarchy, but I believe that it is not unlikely that it actually is.  
> **username_3**: @KristofferArnsfeltHansen: Does that mean you believe that it likely actually is?  
> **username_2**: @username_3: I'm maybe 50/50 on that one.  

---

## 0 answers

