5
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ In fact, $E^{\Sigma_2^p}$ has problems with maximum circuit complexity. ​ ​ $\endgroup$ – user6973 Apr 2 '17 at 0:32
  • $\begingroup$ @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? $\endgroup$ – Dylan McKay Apr 2 '17 at 17:30
  • 1
    $\begingroup$ 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. ​ ​ ​ ​ $\endgroup$ – user6973 Apr 3 '17 at 3:20
  • 1
    $\begingroup$ 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 $\endgroup$ – Ryan Williams Oct 10 '17 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.