17
$\begingroup$

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)

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Thomas supports Monica Apr 9 '17 at 6:37
  • 1
    $\begingroup$ 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? $\endgroup$ – Emil Jeřábek supports Monica Apr 9 '17 at 7:58
  • 1
    $\begingroup$ 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. $\endgroup$ – daniel pehoushek Apr 9 '17 at 9:09
  • 1
    $\begingroup$ 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? ​ ​ ​ ​ $\endgroup$ – user6973 Apr 9 '17 at 9:10
  • 1
    $\begingroup$ 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.) $\endgroup$ – András Salamon Apr 9 '17 at 16:51
9
$\begingroup$

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?).

$\endgroup$
  • 3
    $\begingroup$ 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". $\endgroup$ – Andrew Morgan Apr 10 '17 at 5:14
  • 3
    $\begingroup$ Even though the argument doesn’t give BPEXP, can you get the complexity down to a finite level of EXPH? $\endgroup$ – Emil Jeřábek supports Monica Apr 10 '17 at 13:28
  • 2
    $\begingroup$ @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$. $\endgroup$ – Joshua Grochow Apr 10 '17 at 14:25
  • 2
    $\begingroup$ @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... $\endgroup$ – Joshua Grochow Apr 10 '17 at 14:32
  • 2
    $\begingroup$ @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. $\endgroup$ – Andrew Morgan Apr 10 '17 at 23:09

Your Answer

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

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