<p>Couldn't find this one anywhere... </p>

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

<p>Such an oracle exists for the class$MAEXP$; this was shown by <a href="https://scholar.google.com/scholar?cluster=4287770608656616684&amp;hl=en&amp;as_sdt=0,5&amp;sciodt=0,5">Buhrman, Fortnow, and Thierauf</a>. </p>

CC BY-SA 3.0
2016-10-02T17:35:59.750Z
In the "concluding remarks" of [this paper](http://drops.dagstuhl.de/opus/volltexte/2015/5071/pdf/23.pdf), 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.
Andrew Morgan
CC BY-SA 3.0
2016-10-02T18:56:10.713Z
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).
Ryan Williams
<circuit-complexity><oracles><alternation>
Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$
Ryan Williams
# Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$

(Asked by: username_0 on 2016-10-01)

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](https://scholar.google.com/scholar?cluster=4287770608656616684&hl=en&as_sdt=0,5&sciodt=0,5).

**Tags:** circuit-complexity, oracles, alternation
> **Comments:**
> **username_1**: In the "concluding remarks" of [this paper](http://drops.dagstuhl.de/opus/volltexte/2015/5071/pdf/23.pdf), 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.  
> **username_0**: 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).  

---

## 0 answers

