8
$\begingroup$

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 the expectation is that $\exists\mathbb{R}$ (existential theory of 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 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 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}$?

$\endgroup$
  • 1
    $\begingroup$ For the record: I had an answer but it was just a brain fart. I have deleted it $\endgroup$ – Ryan Williams Sep 18 '19 at 17:37
  • $\begingroup$ @RyanWilliams Who knows, maybe that Allender-Burgisser-Kjeldgaard-Pedersen-Bro Miltersen, "On the complexity of numerical analysis" (Google Scholar link) 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.) $\endgroup$ – Thomas Klimpel Sep 18 '19 at 20:40
  • $\begingroup$ That's likely where Scott got this idea. I was just confused and overly optimistic :) $\endgroup$ – Ryan Williams Sep 18 '19 at 21:32
  • $\begingroup$ $\exists\mathbb{R}$ is not known to be in the counting hierarchy, but I believe that it is not unlikely that it actually is. $\endgroup$ – Kristoffer Arnsfelt Hansen Sep 19 '19 at 8:20
  • $\begingroup$ @KristofferArnsfeltHansen: Does that mean you believe that it likely actually is? $\endgroup$ – user21820 Sep 19 '19 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.