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.

  • $\begingroup$ 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. $\endgroup$ Oct 2, 2016 at 17:35
  • 1
    $\begingroup$ 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). $\endgroup$ Oct 2, 2016 at 18:56


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.