The question whether there exist languages in $\mathsf{E}$ that require circuits of size $\Omega(2^{\delta n})$ for some $\delta > 0$ is open, and this would imply some derandomization results.

Suppose we have a language $L$ which is complete for $\mathsf{E}$. Then, how can $L$ have sub-exponential size circuits? If $L$ has a circuit of size $s(n)$ where $s(n) = o(2^n)$, then we can construct a machine $M$ which evaluates the circuit in time polynomial in $s(n)$ on any input $x$, which implies that $L \in DTIME(poly(s(n))$, which we know cannot happen because of the time hierarchy theorem.

Obviously, I must be missing something here, otherwise why is this such an important and open question?


What you're missing is that it might be hard to construct the circuits. In order for your algorithm to simulate the circuit, it needs to know the circuit, but since the circuit depends on $n$, you can't hard-code it — you'll need to hardcode an infinite number of circuits.

To give a simpler example, consider the following language: $$ \{ x : \text{The $|x|$th Turing machine halts on the empty input} \}. $$ This is an uncomputable language which has constant size circuits.

What could not be the case is that some language in $\mathsf{E}$ has uniform subexponential circuits, for a suitable notion of uniformity (given $n$, you need to be able to construct the circuit in time subexponential in $2^n$). Your argument would work then, since the algorithm would be able to construct the circuit in subexponential time.

| cite | improve this answer | |
  • $\begingroup$ Oh I see. That halting problem example is pretty neat. $\endgroup$ – skankhunt42 Apr 26 '17 at 6:55

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.