Let $\mathsf{CircuitEval}_{s, n}$ be the function which maps an $s$-gate circuit $C$ on $n$ bits and an $n$-bit string $x$ to $C(x)$. Assume that circuits are encoded as an acyclic sequence of assignments $k := g(i, j)$ where $i, j, k$ are wire labels.

I know this is a bit of a funny question, but what is the best known upper bound on the circuit complexity of this problem? There is an $O((s + n)^2)$ single-tape TM computing this function, and so by the Fischer-Pippenger simulation, size $O((s + n)^2 \log(s + n))$ should suffice. The quadratic comes from having to seek back and forth. Is it possible to do better? Is it possible to do in size $O(s + n)$?


I have learned from talking to Ryan Williams (who deserves the credit for my being able to post this answer) that it is known from Paul and Pippenger that Circuit Eval can be decided by a quasilinear time multitape TM and also that there are reductions from multitape TMs to circuits which give only a quasilinear size blowup. That is, Circuit Eval has circuits of size $(n+s)\log^{O(1)}(n+s)$, as per your formulation.

There is a proof of this here on page 6 (see Theorem 3.1 (Folklore)).

  • $\begingroup$ This is perfect, thanks! And thanks to Ryan! $\endgroup$ – Izaak Meckler Apr 3 '17 at 5:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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