<p>The gist of the proof of the proposition you're talking about is to simply cite that <a href="http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/ashraf.pdf" rel="nofollow noreferrer">$EXP\subset P/poly$ implies $EXP=\Sigma_2^p$</a> (there is a short proof of this in the Arora and Barak book in the chapter on circuit complexity), and then you can show using this time $2^{n^{o(1)}}poly(m)$ Circuit SAT algorithm that $\Sigma_2^p\subseteq DTIME[2^{n^{o(1)}}]$, which contradicts the time hierarchy theorem (I can edit in a hint for this if this is desirable).</p>

<ol>
<li><p>If we replaced the assumption, we would no longer get anything we know to be a contradiction in the above argument. As one of the comments mentioned, it is currently open whether $ZPP=EXP$, and even a substantially weaker version of the proposition with a randomized algorithm would give us this separation (note, as the comment says, $BPP$ and $ZPP$ are contained in $P/poly$).</p></li>
<li><p>It is known that if $P = NP$ (so in the flavor of the above, if Circuit SAT has a $poly(n+m)$ time algorithm), we get exponential size lower bounds against $E$. This follows as we know $E^{\Sigma_2^p}$ has exponential size lower bounds, and if $P=NP$, then $E=E^{\Sigma_2^p}$. I'm not sure who this argument first came from, but the idea is that using a $\Sigma_2^p$ oracle, on an input $x$ of length $n$, we can find the lexicographically first truth table of an $n$-bit boolean function with the maximum circuit complexity over $n$-bit boolean functions in time $2^{O(n)}$. After doing this, we can simply look up the value of $x$ in this truth table and output accordingly. In doing this, not only are we computing a function which requires exponential sized circuits, but we are actually showing, as Ricky pointed out in the comments, that $E^{\Sigma_2^p}$ has a language of <em>maximum</em> circuit complexity. <br/><br/> Also, to clarify a point mentioned in the post, to get $P=BPP$, you actually need that $E$ does not even infinitely often have circuits of size $2^{\delta n}$. This does follow from $P=NP$, but it is a stronger hypothesis than $E\not\subset SIZE[2^{\delta n}]$.</p></li>
<li><p>The argument above works for any runtime that falls into $2^{n^{o(1)}}$, so this includes $2^{n^{1/\log\log(n)}}$.</p></li>
</ol>

CC BY-SA 3.0
2017-04-02T17:30:08.347Z
@RickyDemer Good point! I added a very brief explanation of this. Do you happen to know the source one would usually use for citing this fact in general of if it considered to be folklore?
Dylan McKay
CC BY-SA 3.0
2017-10-10T00:38:58.523Z
Miltersen, Vinodchandran, and Watanabe '99 (https://link-springer-com.libproxy.mit.edu/chapter/10.1007%2F3-540-48686-0_21) is probably the right reference for "$E^{\Sigma_2 P}$ has functions with maximum circuit complexity". Some additional history (from the 70s-80s) can be found here: https://people.csail.mit.edu/meyer/stock-circuit-jacm.pdf
Ryan Williams
CC BY-SA 3.0
2017-04-01T17:33:08.463Z
2017-04-02T17:26:19.943Z
2017-04-02T17:26:19.943Z
Dylan McKay
<p>In <a href="https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf" rel="noreferrer">here</a> on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'.</p>

<ol>
<li><p>Can we have <em>randomized</em> $2^{n^{o(1)}}poly(m)$ time in above statement?</p></li>
<li><p>Is there a similar result that would give $E\not\subseteq SIZE(2^{\delta n})$ (this would give $P=BPP$)?</p></li>
<li><p>How large can $o(1)$ be in the statement above and in 1. if applicable (can it be as large as $1/\log\log n$)?</p></li>
</ol>

<big-picture><derandomization>
Implications of faster randomized $CIRCUIT SAT$ algorithm
Turbo
# Implications of faster randomized $CIRCUIT SAT$ algorithm

(Asked by: username_0 on 2017-03-26)

In [here](https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf) on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'.

1. Can we have *randomized* $2^{n^{o(1)}}poly(m)$ time in above statement?
2. Is there a similar result that would give $E\not\subseteq SIZE(2^{\delta n})$ (this would give $P=BPP$)?
3. How large can $o(1)$ be in the statement above and in 1. if applicable (can it be as large as $1/\log\log n$)?

**Tags:** big-picture, derandomization


---

## 1 answers

### Answer by username_1 on 2017-04-01. Score: 7 | Accepted answer

The gist of the proof of the proposition you're talking about is to simply cite that [$EXP\subset P/poly$ implies $EXP=\Sigma\_2^p$](http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/ashraf.pdf) (there is a short proof of this in the Arora and Barak book in the chapter on circuit complexity), and then you can show using this time $2^{n^{o(1)}}poly(m)$ Circuit SAT algorithm that $\Sigma\_2^p\subseteq DTIME[2^{n^{o(1)}}]$, which contradicts the time hierarchy theorem (I can edit in a hint for this if this is desirable).

1. If we replaced the assumption, we would no longer get anything we know to be a contradiction in the above argument. As one of the comments mentioned, it is currently open whether $ZPP=EXP$, and even a substantially weaker version of the proposition with a randomized algorithm would give us this separation (note, as the comment says, $BPP$ and $ZPP$ are contained in $P/poly$).
2. It is known that if $P = NP$ (so in the flavor of the above, if Circuit SAT has a $poly(n+m)$ time algorithm), we get exponential size lower bounds against $E$. This follows as we know $E^{\Sigma\_2^p}$ has exponential size lower bounds, and if $P=NP$, then $E=E^{\Sigma\_2^p}$. I'm not sure who this argument first came from, but the idea is that using a $\Sigma\_2^p$ oracle, on an input $x$ of length $n$, we can find the lexicographically first truth table of an $n$-bit boolean function with the maximum circuit complexity over $n$-bit boolean functions in time $2^{O(n)}$. After doing this, we can simply look up the value of $x$ in this truth table and output accordingly. In doing this, not only are we computing a function which requires exponential sized circuits, but we are actually showing, as Ricky pointed out in the comments, that $E^{\Sigma\_2^p}$ has a language of *maximum* circuit complexity.   
     
    Also, to clarify a point mentioned in the post, to get $P=BPP$, you actually need that $E$ does not even infinitely often have circuits of size $2^{\delta n}$. This does follow from $P=NP$, but it is a stronger hypothesis than $E\not\subset SIZE[2^{\delta n}]$.
3. The argument above works for any runtime that falls into $2^{n^{o(1)}}$, so this includes $2^{n^{1/\log\log(n)}}$.

> **Comments:**
> **username_1**: @RickyDemer Good point! I added a very brief explanation of this. Do you happen to know the source one would usually use for citing this fact in general of if it considered to be folklore?  
> **username_2**: Miltersen, Vinodchandran, and Watanabe '99 (https://link-springer-com.libproxy.mit.edu/chapter/10.1007%2F3-540-48686-0_21) is probably the right reference for "$E^{\Sigma_2 P}$ has functions with maximum circuit complexity". Some additional history (from the 70s-80s) can be found here: https://people.csail.mit.edu/meyer/stock-circuit-jacm.pdf  

---

