# Implications of faster randomized $CIRCUIT SAT$ algorithm

In here 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$)?

• If ​ ZPP = EXP ​ then circuit-SAT has a randomized polynomial-time algorithm $\hspace{1.86 in}$ and ​ EXP = ZPP $\subseteq$ BPP $\subset$ P/poly . ​ ​ ​ ​ – user6973 Mar 30 '17 at 1:44

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$ (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)}}$.

• In fact, $E^{\Sigma_2^p}$ has problems with maximum circuit complexity. ​ ​ – user6973 Apr 2 '17 at 0:32
• @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 Apr 2 '17 at 17:30
• The ending paragraph of page 7 and the starting paragraph of page 8 mean this paper is a reference for most of that. ​ Otherwise, the result seems to be folklore. ​ ​ ​ ​ – user6973 Apr 3 '17 at 3:20
• Miltersen, Vinodchandran, and Watanabe '99 (link-springer-com.libproxy.mit.edu/chapter/…) 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: people.csail.mit.edu/meyer/stock-circuit-jacm.pdf – Ryan Williams Oct 10 '17 at 0:38