# Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$

Couldn't find this one anywhere...

It's an open problem whether $\Sigma_2 EXP$ problems have exponential-size circuit complexity. Is there an oracle relative to which $\Sigma_2 EXP$ has $2^{o(n)}$ size circuits? $2^{n^{o(1)}}$ size?

Such an oracle exists for the class$MAEXP$; this was shown by Buhrman, Fortnow, and Thierauf.

• In the "concluding remarks" of this paper, it's claimed that "one can prove that $\mathsf{S}^2_{exp} \ne \mathsf{BPP}$. I don't immediately see it, but I suspect it either goes by some diagonalization against small circuits, or else against $\mathsf{S}^2_p$, and it seems reasonable that a similar argument might extend to your situation. Oct 2, 2016 at 17:35
• That class (and $\Sigma_2 EXP$) isn't in P/poly (by a variant of the Karp-Lipton theorem), which is why it's not in BPP. However this argument only yields circuit size lower bounds for functions $s(n)$ such that $s(s(n)) \leq 2^n$ (half-exponential). Oct 2, 2016 at 18:56