<p>I believe if you trace through the argument given, e.g., in Section 4.1 of <a href="http://www3.cs.stonybrook.edu/~keriko/survey2.pdf" rel="nofollow noreferrer">Ker-I Ko's survey</a>, 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.</p>

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

<ul>
<li><p>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.</p></li>
<li><p>Translating into circuit lower bounds, this means we're considering bounded-depth circuits on $2^{t(n)}$ inputs.</p></li>
<li><p>The requirement (see p. 15 of Ko) we need $m(n)$ to satisfy $\frac{1}{10} 2^{m/(d-1)} &gt; 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.</p></li>
<li><p>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.</p></li>
<li><p><a href="https://eccc.weizmann.ac.il/report/2012/116/" rel="nofollow noreferrer">Trevisan and Xue</a> (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.</p></li>
<li><p>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.</p></li>
</ul>

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

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

<ul>
<li><p>...to a <a href="https://eccc.weizmann.ac.il/report/2011/136/" rel="nofollow noreferrer">pseudodeterministic/Bellagio</a> algorithm (see Andrew Morgan's comment below), one would get that $\mathsf{BPEXP} \not\subseteq \mathsf{P/poly}$; or</p></li>
<li><p>...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 (<a href="https://cstheory.stackexchange.com/a/37813/129">cf. $\mathsf{NPSV}$</a>), it would imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$; or</p></li>
<li><p>... to a deterministic algorithm, one would get $\mathsf{EXP} \not\subseteq \mathsf{P/poly}$.</p></li>
</ul>

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

CC BY-SA 3.0
2017-04-10T01:57:05.803Z
Thank you very much for the answer Joshua!!  I really appreciate it.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-10T01:58:54.173Z
It seems that if we really do have an oracle $A \in BPEXP$ such that $PSPACE^A \neq PH^A$, then we have $BPEXP \nsubseteq P/poly$.
Michael Wehar
CC BY-SA 3.0
2017-04-10T02:01:55.173Z
Has someone already proven $BPEXP \nsubseteq P/poly$?  As @RickyDemer already said above, basically $EXP^{NP}$ is the largest class that could still possibly be a subset of $P/poly$.
Michael Wehar
CC BY-SA 3.0
2017-04-10T02:42:48.707Z
Oh, hm, I must be misinterpreting something about Trevisan-Xue, since I'm pretty sure the smallest class known not to be in P/poly is $MA_{EXP}$, and this proof seems surprisingly easy to get such a result for BPEXP. I'll think about it a bit more.
Joshua Grochow
CC BY-SA 3.0
2017-04-10T03:06:31.877Z
Oh wait, is it known that $BPEXP \subseteq P/poly \Rightarrow PSPACE=PH$? That was a key part of your proof for $NEXP$...
Joshua Grochow
CC BY-SA 3.0
2017-04-10T03:41:22.793Z
Yep, it is.  In particular, it is known that if $PSPACE \subseteq P/poly$, then $PSPACE = \Sigma_2 P$.  Furthermore, because $PSPACE \subseteq BPEXP$, if $BPEXP \subseteq P/poly$, then $PSPACE = \Sigma_2 P$.
Michael Wehar
CC BY-SA 3.0
2017-04-10T03:42:24.487Z
See here for more info: https://en.wikipedia.org/wiki/P/poly
Michael Wehar
CC BY-SA 3.0
2017-04-10T03:55:31.747Z
Oh yeah, I knew that :]. Okay, so back to me looking more into Trevisan-Xue...
Joshua Grochow
CC BY-SA 3.0
2017-04-10T03:59:48.453Z
Ok, great!  Let me know what you come up with and we can discuss further.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-10T05:14:45.507Z
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
CC BY-SA 3.0
2017-04-10T11:16:24.010Z
@AndrewMorgan: Ah, right! You'd need a $\mathsf{BPPSV}$ / pseudodeterministic / Bellagio algorithm to actually decide the oracle. But I think searching over all seeds should still give the deterministic time bound in my answer, as one can just search thru seeds exhaustively and use the first one that works (which is then a deterministically chosen "canonical" seed, even though it takes exponentially more time to find it).
Joshua Grochow
CC BY-SA 3.0
2017-04-10T13:28:20.843Z
Even though the argument doesn’t give BPEXP, can you get the complexity down to a finite level of EXPH?
Emil Jeřábek
CC BY-SA 3.0
2017-04-10T14:25:17.293Z
@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
CC BY-SA 3.0
2017-04-10T14:32:48.110Z
@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
CC BY-SA 3.0
2017-04-10T17:37:37.567Z
@JoshuaGrochow: I'm not sure your verification step will run in time. We're diagonalizing against $\Sigma_k$ machines whose running times can be polynomials of any degree---brute forcing through all the nondeterminism takes time more than $2^{n^c}$ for any fixed $c$. Is there a better way? Maybe something can be done by supposing that the circuit lower bound fails (eg MA_EXP in P/poly) and then leveraging that. But that seems to be getting close to the ordinary proof that MA_EXP isn't in P/poly... (which is on the bottom of p. 297 of Arora-Barak).
Andrew Morgan
CC BY-SA 3.0
2017-04-10T17:58:37.230Z
@AndrewMorgan: I think that is already taken into account in the third bullet point: $2^{m/(d-1)} > d p_n(m(n))$ where $p_n$ is the $n$-th polynomial. For $m$ sufficiently large (as I say, $~2^n$), it works against all polynomials simultaneously. Or am I misunderstanding your objection?
Joshua Grochow
CC BY-SA 3.0
2017-04-10T18:04:12.487Z
@AndrewMorgan: Oh wait, or you were just talking about trying to get it down to $\mathsf{MA_{EXP}}$? I thought you were pointing out a flaw in the original argument.
Joshua Grochow
CC BY-SA 3.0
2017-04-10T21:34:44.823Z
@JoshuaGrochow Yeah, I was objecting in the way you suspected. (And then mused on how to work around it.) Sorry I said it so confusingly; let me try again: In the $n$-th stage, $m(n)$ is the length where we make the main choices for our oracle, and $p_n(m)$ bounds the running time of the machine we're diagonalizing against. We want to use only $2^{m^c}$ time in the construction in order to be sufficiently constructive. However, the argument involves a circuit of size $2^{p_n(m)}$, and we can't actually afford to write down that whole thing. In particular, we can't just naively evaluate it.
Andrew Morgan
CC BY-SA 3.0
2017-04-10T21:59:58.937Z
@AndrewMorgan: By choosing $m(n)=2^n$, we get that $2^{p_n(m(n))} \sim 2^{2^{n^2}}$, so we're dealing with circuits of size roughly $2^{2^{n^2}}$, which can be evaluated in roughly $2^{2^{n^2}}$ time. Even if we needed to make $2^{2^{O(n^2)}}$ such evaluations, the total time is still $2^{2^{O(n^2}}$.
Joshua Grochow
CC BY-SA 3.0
2017-04-10T22:28:37.513Z
@JoshuaGrochow Right, but in order to say something like "the oracle is in EXP" or similar, one needs to show how to decide whether a given query q is in the oracle in time exponential in |q|. If we try to decide some q of length $m(n)$ (an input length where the oracle is nontrivial), then $2^{2^{n^2}} = 2^{m^{\log(m)}}$ time is too much.
Andrew Morgan
CC BY-SA 3.0
2017-04-10T22:43:18.633Z
@AndrewMorgan: I never claimed the oracle was in $\mathsf{EXP}$, I claimed it was in $\mathsf{EEXP}$ (in particular, $\mathsf{DTIME}(2^{2^{O(|q|^2)}})$; note that in the answer I wrote $n$ instead of $|q|$, but this was an overuse of the parameter $n$ - this $n$ isn't the same as the $n$ in the construction). Given $q$ of length $2^k$, we can decide if $q$ is in the oracle in time $\sim 2^{2^{k^2}} = 2^{|q|^{\log |q|}}$, but $2^{|q|^{\log |q|}} = 2^{2^{\log^2|q|}} \leq 2^{2^{O(|q|^2)}}$ (so actually, the final upper bound on the oracle is $2^{quasi-poly(|q|)}$ rather than $2^{exp(|q|^2)}$).
Joshua Grochow
CC BY-SA 3.0
2017-04-10T23:09:13.097Z
@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
CC BY-SA 3.0
2017-04-11T04:17:41.310Z
@AndrewMorgan Thank you both for going into all of these details!  I really appreciate it.  This has definitely helped me understand a bit better.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-09T21:23:46.880Z
2017-04-10T11:25:58.867Z
2017-04-13T12:32:28.080Z
Joshua Grochow
<p><strong>Background</strong></p>

<blockquote>
  <p>It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$.</p>
  
  <p>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.</p>
</blockquote>

<p><strong>Question</strong></p>

<blockquote>
  <p>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$?</p>
  
  <p>Do we have any oracle $A$ such that $PSPACE^A \neq PH^A$ and $A$ has a known complexity upper bound?</p>
</blockquote>

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

<p><strong>Update with details on a lower bound technique</strong></p>

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

<blockquote>
  <p><strong>Proof Sketch:</strong> Suppose that $PSPACE = PH$.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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$.</p>
  
  <p>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.</p>
</blockquote>

<p>Now, we can show the conditional lower bound.</p>

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

<blockquote>
  <p><strong>Proof Sketch:</strong> 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. </p>
  
  <p>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$.</p>
  
  <p>(see <a href="https://en.wikipedia.org/wiki/P/poly" rel="noreferrer">here</a> for some details on known results for P/poly)</p>
</blockquote>

CC BY-SA 3.0
2017-04-09T06:24:55.680Z
Relevant survey paper on relativized separation results: Constructing Oracles by Lower Bound
Techniques for Circuits by Ker-I Ko
Michael Wehar
CC BY-SA 3.0
2017-04-09T06:37:22.270Z
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 Steinke
CC BY-SA 3.0
2017-04-09T07:58:00.000Z
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
CC BY-SA 3.0
2017-04-09T08:09:54.470Z
@EmilJeřábek That is a great point! So what are the two (or more) variants? Is it that one notion of relativized PSPACE only allows you to make polynomial sized queries because the space used on the query tape counts for the space complexity while the other notion doesn't count the space used on the query tape allowing you to write an exponential size query, but requiring that the tape be write only and that the tape is cleared after each query is made?
Michael Wehar
CC BY-SA 3.0
2017-04-09T08:10:03.863Z
Please correct me if I'm wrong, but I think that the first notion is commonly used and is sufficient for obtaining the relativized separation results that I was referring to in the question.
Michael Wehar
CC BY-SA 3.0
2017-04-09T08:14:13.707Z
Yes, on page 3 of the reference that I mentioned, it says, "including the space of the query tape".  In other words, the first notion where the space on the query tape is counted is the one that I'm focusing on.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-09T09:09:04.000Z
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
CC BY-SA 3.0
2017-04-09T16:41:49.433Z
@RickyDemer Please feel free to share your lower bound!  When I said "have ramifications in structural complexity theory", I had a certain lower bound in mind.  In particular, I think I can show that if there exists an oracle $A \in NEXP$ such that $PSPACE^A \neq PH^A$, then $NEXP \nsubseteq P/poly$.
Michael Wehar
CC BY-SA 3.0
2017-04-09T16:51:21.800Z
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
CC BY-SA 3.0
2017-04-09T17:05:03.570Z
@danielpehoushek Hi Daniel, I don't know much about QPSACE, but I just downloaded your paper.  With #Q, I think it's an interesting idea to count the number of quantifier arrangements that make a formula valid.  I'm not quite sure that I understand QSPACE (the decision problem) though.  Any help would be greatly appreciated.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-09T17:07:25.200Z
@AndrásSalamon Thank you András!  That could very well be the case.  I guess I will write-up the result that I was referring to.  It's nice to hear from you.  Hope that all is going well.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-09T18:16:31.340Z
@RickyDemer Very neat!!  Thank you for sharing.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-09T18:18:17.183Z
@RickyDemer Thank you Ricky!!  I appreciate the strengthening.  It helps.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-09T18:35:16.197Z
@RickyDemer That is very helpful information!!  Thank you.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-10T04:08:23.330Z
@RickyDemer Thank you again!  I started looking a little deeper into the literature on this topic.  I took a look at "Oracles Are Subtle But Not Malicious" and "Nonrelativizing Separations".  :)
Michael Wehar
CC BY-SA 3.0
2017-04-10T13:35:11.267Z
(Continuing the comments way up.) Another possibility is not to count the oracle tape against the space quota, and not to erase it (or move the head) after each use. On the other hand, when doing this, it might be also reasonable to limit the *time* of the computation to something exponential in the space quota. IMHO for a general-purpose definition of relativized space classes, it is indeed more natural *not* to count the oracle tape in the space allowance. For example, it would make no sense to demand that a relativized log-space algorithm may only make logarithmic-length queries. ...
Emil Jeřábek
CC BY-SA 3.0
2017-04-10T13:38:33.103Z
... There is nothing wrong with PSPACE algorithms making exponentially long queries *per se*; after all, no one bats an eyelid that relativized EXP algorithms may make exponentially long queries. Now, for the particular problem of relativized separation of PH and PSPACE, it seems that polynomially limited queries is the more interesting model, as relativized PH inherently has this limitation. But that’s why I asked for clarification.
Emil Jeřábek
CC BY-SA 3.0
2017-04-10T14:25:24.277Z
@EmilJeřábek Thank you very much for the follow-up in regards to the oracle model.  That makes sense.  I wonder if there has been much work on relativized complexity classes with restricted query length?  For example, relativized exponential time with quasi-polynomial query length.
Michael Wehar
<cc.complexity-theory><oracles><relativization><pspace><structural-complexity>
What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?
Michael Wehar
# What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

(Asked by: username_0 on 2017-04-09)

**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](https://en.wikipedia.org/wiki/P/poly) for some details on known results for P/poly)

**Tags:** cc.complexity-theory, oracles, relativization, pspace, structural-complexity
> **Comments:**
> **username_0**: Relevant survey paper on relativized separation results: Constructing Oracles by Lower Bound Techniques for Circuits by Ker-I Ko  
> **username_1**: 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.  
> **username_2**: 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?  
> **username_0**: @EmilJeřábek That is a great point! So what are the two (or more) variants? Is it that one notion of relativized PSPACE only allows you to make polynomial sized queries because the space used on the query tape counts for the space complexity while the other notion doesn't count the space used on the query tape allowing you to write an exponential size query, but requiring that the tape be write only and that the tape is cleared after each query is made?  
> **username_0**: Please correct me if I'm wrong, but I think that the first notion is commonly used and is sufficient for obtaining the relativized separation results that I was referring to in the question.  
> **username_0**: Yes, on page 3 of the reference that I mentioned, it says, "including the space of the query tape".  In other words, the first notion where the space on the query tape is counted is the one that I'm focusing on.  :)  
> **username_3**: 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.  
> **username_0**: @RickyDemer Please feel free to share your lower bound!  When I said "have ramifications in structural complexity theory", I had a certain lower bound in mind.  In particular, I think I can show that if there exists an oracle $A \in NEXP$ such that $PSPACE^A \neq PH^A$, then $NEXP \nsubseteq P/poly$.  
> **username_4**: 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.)  
> **username_0**: @danielpehoushek Hi Daniel, I don't know much about QPSACE, but I just downloaded your paper.  With #Q, I think it's an interesting idea to count the number of quantifier arrangements that make a formula valid.  I'm not quite sure that I understand QSPACE (the decision problem) though.  Any help would be greatly appreciated.  :)  
> **username_0**: @AndrásSalamon Thank you András!  That could very well be the case.  I guess I will write-up the result that I was referring to.  It's nice to hear from you.  Hope that all is going well.  :)  
> **username_0**: @RickyDemer Very neat!!  Thank you for sharing.  :)  
> **username_0**: @RickyDemer Thank you Ricky!!  I appreciate the strengthening.  It helps.  :)  
> **username_0**: @RickyDemer That is very helpful information!!  Thank you.  :)  
> **username_0**: @RickyDemer Thank you again!  I started looking a little deeper into the literature on this topic.  I took a look at "Oracles Are Subtle But Not Malicious" and "Nonrelativizing Separations".  :)  
> **username_2**: (Continuing the comments way up.) Another possibility is not to count the oracle tape against the space quota, and not to erase it (or move the head) after each use. On the other hand, when doing this, it might be also reasonable to limit the *time* of the computation to something exponential in the space quota. IMHO for a general-purpose definition of relativized space classes, it is indeed more natural *not* to count the oracle tape in the space allowance. For example, it would make no sense to demand that a relativized log-space algorithm may only make logarithmic-length queries. ...  
> **username_2**: ... There is nothing wrong with PSPACE algorithms making exponentially long queries *per se*; after all, no one bats an eyelid that relativized EXP algorithms may make exponentially long queries. Now, for the particular problem of relativized separation of PH and PSPACE, it seems that polynomially limited queries is the more interesting model, as relativized PH inherently has this limitation. But that’s why I asked for clarification.  
> **username_0**: @EmilJeřábek Thank you very much for the follow-up in regards to the oracle model.  That makes sense.  I wonder if there has been much work on relativized complexity classes with restricted query length?  For example, relativized exponential time with quasi-polynomial query length.  

---

## 1 answers

### Answer by username_5 on 2017-04-09. Score: 9 | Accepted answer

I believe if you trace through the argument given, e.g., in Section 4.1 of [Ker-I Ko's survey](http://www3.cs.stonybrook.edu/~keriko/survey2.pdf), 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](https://eccc.weizmann.ac.il/report/2012/116/) (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](https://eccc.weizmann.ac.il/report/2011/136/) 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}$](https://cstheory.stackexchange.com/a/37813/129)), 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?).

> **Comments:**
> **username_0**: Thank you very much for the answer Joshua!!  I really appreciate it.  :)  
> **username_0**: It seems that if we really do have an oracle $A \in BPEXP$ such that $PSPACE^A \neq PH^A$, then we have $BPEXP \nsubseteq P/poly$.  
> **username_0**: Has someone already proven $BPEXP \nsubseteq P/poly$?  As @RickyDemer already said above, basically $EXP^{NP}$ is the largest class that could still possibly be a subset of $P/poly$.  
> **username_5**: Oh, hm, I must be misinterpreting something about Trevisan-Xue, since I'm pretty sure the smallest class known not to be in P/poly is $MA_{EXP}$, and this proof seems surprisingly easy to get such a result for BPEXP. I'll think about it a bit more.  
> **username_5**: Oh wait, is it known that $BPEXP \subseteq P/poly \Rightarrow PSPACE=PH$? That was a key part of your proof for $NEXP$...  
> **username_0**: Yep, it is.  In particular, it is known that if $PSPACE \subseteq P/poly$, then $PSPACE = \Sigma_2 P$.  Furthermore, because $PSPACE \subseteq BPEXP$, if $BPEXP \subseteq P/poly$, then $PSPACE = \Sigma_2 P$.  
> **username_0**: See here for more info: https://en.wikipedia.org/wiki/P/poly  
> **username_5**: Oh yeah, I knew that :]. Okay, so back to me looking more into Trevisan-Xue...  
> **username_0**: Ok, great!  Let me know what you come up with and we can discuss further.  :)  
> **username_6**: 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".  
> **username_5**: @AndrewMorgan: Ah, right! You'd need a $\mathsf{BPPSV}$ / pseudodeterministic / Bellagio algorithm to actually decide the oracle. But I think searching over all seeds should still give the deterministic time bound in my answer, as one can just search thru seeds exhaustively and use the first one that works (which is then a deterministically chosen "canonical" seed, even though it takes exponentially more time to find it).  
> **username_2**: Even though the argument doesn’t give BPEXP, can you get the complexity down to a finite level of EXPH?  
> **username_5**: @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$.  
> **username_5**: @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...  
> **username_6**: @JoshuaGrochow: I'm not sure your verification step will run in time. We're diagonalizing against $\Sigma_k$ machines whose running times can be polynomials of any degree---brute forcing through all the nondeterminism takes time more than $2^{n^c}$ for any fixed $c$. Is there a better way? Maybe something can be done by supposing that the circuit lower bound fails (eg MA_EXP in P/poly) and then leveraging that. But that seems to be getting close to the ordinary proof that MA_EXP isn't in P/poly... (which is on the bottom of p. 297 of Arora-Barak).  
> **username_5**: @AndrewMorgan: I think that is already taken into account in the third bullet point: $2^{m/(d-1)} > d p_n(m(n))$ where $p_n$ is the $n$-th polynomial. For $m$ sufficiently large (as I say, $~2^n$), it works against all polynomials simultaneously. Or am I misunderstanding your objection?  
> **username_5**: @AndrewMorgan: Oh wait, or you were just talking about trying to get it down to $\mathsf{MA_{EXP}}$? I thought you were pointing out a flaw in the original argument.  
> **username_6**: @JoshuaGrochow Yeah, I was objecting in the way you suspected. (And then mused on how to work around it.) Sorry I said it so confusingly; let me try again: In the $n$-th stage, $m(n)$ is the length where we make the main choices for our oracle, and $p_n(m)$ bounds the running time of the machine we're diagonalizing against. We want to use only $2^{m^c}$ time in the construction in order to be sufficiently constructive. However, the argument involves a circuit of size $2^{p_n(m)}$, and we can't actually afford to write down that whole thing. In particular, we can't just naively evaluate it.  
> **username_5**: @AndrewMorgan: By choosing $m(n)=2^n$, we get that $2^{p_n(m(n))} \sim 2^{2^{n^2}}$, so we're dealing with circuits of size roughly $2^{2^{n^2}}$, which can be evaluated in roughly $2^{2^{n^2}}$ time. Even if we needed to make $2^{2^{O(n^2)}}$ such evaluations, the total time is still $2^{2^{O(n^2}}$.  
> **username_6**: @JoshuaGrochow Right, but in order to say something like "the oracle is in EXP" or similar, one needs to show how to decide whether a given query q is in the oracle in time exponential in |q|. If we try to decide some q of length $m(n)$ (an input length where the oracle is nontrivial), then $2^{2^{n^2}} = 2^{m^{\log(m)}}$ time is too much.  
> **username_5**: @AndrewMorgan: I never claimed the oracle was in $\mathsf{EXP}$, I claimed it was in $\mathsf{EEXP}$ (in particular, $\mathsf{DTIME}(2^{2^{O(|q|^2)}})$; note that in the answer I wrote $n$ instead of $|q|$, but this was an overuse of the parameter $n$ - this $n$ isn't the same as the $n$ in the construction). Given $q$ of length $2^k$, we can decide if $q$ is in the oracle in time $\sim 2^{2^{k^2}} = 2^{|q|^{\log |q|}}$, but $2^{|q|^{\log |q|}} = 2^{2^{\log^2|q|}} \leq 2^{2^{O(|q|^2)}}$ (so actually, the final upper bound on the oracle is $2^{quasi-poly(|q|)}$ rather than $2^{exp(|q|^2)}$).  
> **username_6**: @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.  
> **username_0**: @AndrewMorgan Thank you both for going into all of these details!  I really appreciate it.  This has definitely helped me understand a bit better.  :)  

---

