7
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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$
    – Andrew Morgan
    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$
    – Ryan Williams
    Oct 2, 2016 at 18:56

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.