# What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Background

It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$.

It is even known that the separation holds relative to a random oracle. Informally, one may interpret this to mean that there are many oracles for which $PSPACE$ and $PH$ are separate.

Question

How complicated are these oracles that separate $PSPACE$ from $PH$. In particular, is there an oracle $A \in DTIME(2^{2^{n}})$ such that $PSPACE^A \neq PH^A$?

Do we have any oracle $A$ such that $PSPACE^A \neq PH^A$ and $A$ has a known complexity upper bound?

Note: the existence of such an oracle may have ramifications in structural complexity theory. See the following update below for further details.

Update with details on a lower bound technique

Claim: If $PSPACE = PH$, then for all oracles $A \in P/poly$, $PSPACE^A = PH^A$.

Proof Sketch: Suppose that $PSPACE = PH$.

Let an oracle $A \in P/poly$ be given. We can build a polynomial time $\Sigma_2$ oracle Turing machine $M$ that for a given length $n$, guesses a circuit of size $p(n)$ using an existential quantification and verifies that the circuit decides $A$ by comparing the evaluation of the circuit and the query result for every length $n$ string using a universal quantification.

Further, consider a decision problem that I'm referring to as quantified Boolean circuit (QBC) where you are given a quantified boolean circuit and want to know if it valid (similar to QBF). This problem is PSPACE-complete because QBF is PSPACE-complete.

By assumption, it follows that QBC $\in PH$. Let's say $QBC \in \Sigma_k$ for some $k$ sufficiently large. Let $N$ denote a polynomial time $\Sigma_k$ Turing machine that solves QBC.

We can intermingle the computation of $M$ and $N$ (similar to what is done in the proof of the Karp-Lipton theorem) to get a polynomial time $\Sigma_k$ oracle Turing machine that solves $QBC^A$.

Informally, this new machine takes as input an oracle QBC (that is a QBC with oracle gates). Then, it computes a circuit that computes $A$ on inputs of length $n$ (simultaneously pealing off the first two quantifiers). Next, it replaces the oracle gates in the oracle QBC with the circuit for $A$. Finally, it proceeds to apply the remainder of the polynomial time $\Sigma_k$ algorithm for solving $QBC$ on this modified instance.

Now, we can show the conditional lower bound.

Corollary: If there exists an oracle $A \in NEXP$ such that $PSPACE^A \neq PH^A$, then $NEXP \nsubseteq P/poly$.

Proof Sketch: Suppose that there exists $A \in NEXP$ such that $PSPACE^A \neq PH^A$. If $NEXP \subseteq P/poly$, then we would get a contradiction.

In particular, if $NEXP \subseteq P/poly$, then by the claim above we have $PSPACE \neq PH$. However, it is known that $NEXP \subseteq P/poly$ implies that $PSPACE = PH$.

(see here for some details on known results for P/poly)

• It's probably worth mentioning that it's conjectured that PSPACE$\ne$PH. i.e. a trivial oracle would do, but we just can't prove it. – Thomas Apr 9 '17 at 6:37
• How, exactly, do you define relativized PSPACE? More than one possibility appears in the literature. In particular, are oracle queries assumed to be polynomially bounded? – Emil Jeřábek Apr 9 '17 at 7:58
• Do you include "The construction of Q formulas," large monotone boolean formulas that decide all 2^n qbfs of the original formula, in PH? See Introduction to QSpace, 2002 Satisfiability Conference, International workshop on QBFS, for more on Q formulas. – daniel pehoushek Apr 9 '17 at 9:09
• I believe I can show, as a lower bound, that such an $A$ being in SEH would "have ramifications in structural complexity theory." ​ Should I post that fairly soon (which might mean tomorrow or might mean in 30 minutes), or leave this unanswered longer so you're more likely to get an answer with a class that suffices? ​ ​ ​ ​ – user6973 Apr 9 '17 at 9:10
• Given that random oracles have high Kolmogorov complexity, I would expect any computable upper bound on such oracles to have notable consequences. Strong upper bounds such as singly-exponential should have strong consequences. (Of course, this argument is purely heuristic and I currently have no idea how to make it rigorous.) – András Salamon Apr 9 '17 at 16:51

I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close.

In particular, using the translation between oracle separations and circuit lower bounds, and following Ko's notation, we have the following:

• We will diagonalize over strings of length $t(n) = p_n(m(n))$ where $p_n(x) = x^n + n$ is "the" $n$-th polynomial (in some enumeration of poly-time algorithms) and $m(n)$ will be specified below.

• Translating into circuit lower bounds, this means we're considering bounded-depth circuits on $2^{t(n)}$ inputs.

• The requirement (see p. 15 of Ko) we need $m(n)$ to satisfy $\frac{1}{10} 2^{m/(d-1)} > d p_n(m(n))$ for all $n$. Here $d$ is the depth of the circuits we want to diagonalize against, or equivalently the level $\mathsf{\Sigma_d^p}$ of $\mathsf{PH}$ we want to diagonalize against. To diagonalize against all of $\mathsf{PH}$, simply choose $d$ to be a function of $n$ that is $\omega(1)$; we may choose such a $d$ that grows arbitrarily slowly, though (perhaps subject to some computability assumption on $d(n)$, but that should be no obstacle). If we make the guess that $d(n)$ is constant (even though it's not, but it will grow arbitrarily slowly), then we see that $m(n)$ around $2^n$ should work.

• This means that $t(n) \sim 2^{n^2}$, so we are looking for a lower bound against circuits with $\sim 2^{2^{n^2}}$ inputs.

• Trevisan and Xue (CCC '13) showed that one can find an assignment on which a given bounded-depth circuit on $N$ inputs doesn't compute PARITY with a seed of $polylog(N)$ length.

• For us $N=2^{2^{n^2}}$, so $polylog(N) = 2^{O(n^2)}$. We can brute force over such seeds in $2^{2^{O(n^2)}}$ time and use the first one that works.

To replace the $n^2$ with $nf(n)$, just let $p_n(x) = x^{f(n)} + f(n)$ instead.

Interestingly, if I'm understanding correctly, I believe this implies that if one could improve the Trevisan-Xue...

• ...to a pseudodeterministic/Bellagio algorithm (see Andrew Morgan's comment below), one would get that $\mathsf{BPEXP} \not\subseteq \mathsf{P/poly}$; or

• ...to a nondeterministic algorithm that guessed $polylog(N)$ bits but then ran in $poly(N)$ time, and such that on any accepting path it makes the same output (cf. $\mathsf{NPSV}$), it would imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$; or

• ... to a deterministic algorithm, one would get $\mathsf{EXP} \not\subseteq \mathsf{P/poly}$.

On the one hand, this suggests why derandomizing the switching lemma further should be hard - an argument which I'm not sure was known before! On the other hand, this strikes me as a kind of interesting take on hardness versus randomness (or is this actually a new thing, oracles versus randomness?).

• One challenge that's glossed over here is that the oracle that's constructed has to be a single, fixed oracle, so that deciding it is in BPEXP or whatever. If you just pick a random seed of a good generator, then, while you do get some oracle that works, you don't necessarily get a decision procedure for that oracle, since different seeds give (in general) different oracles. You'd have to do something more, like finding a canonical seed, in order to make the construction actually "constructive". – Andrew Morgan Apr 10 '17 at 5:14
• Even though the argument doesn’t give BPEXP, can you get the complexity down to a finite level of EXPH? – Emil Jeřábek Apr 10 '17 at 13:28
• @EmilJeřábek: Without checking the details, I think $\mathsf{\Sigma_3 EXP}$ should work. Guess a seed using $\exists$, verify it works using $\forall$, and then verify that it is the lexicographically least seed using $\neg\exists\forall = \forall \exists \neg$, for a total of $\exists\forall\exists$. – Joshua Grochow Apr 10 '17 at 14:25
• @EmilJerabek: Of course, if we could at least get this down to $\mathsf{MA_{EXP}}$ that would be even better (not improvable without proving new circuit lower bounds), but I don't yet see how to do that... – Joshua Grochow Apr 10 '17 at 14:32
• @JoshuaGrochow Yeah, your original post seems fine. I was objecting to your reply to Emil that hypothesized the oracle can be made in EXPH, where the running time is singly-exponential. In retrospect I should have been more clear about that. – Andrew Morgan Apr 10 '17 at 23:09