<p>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.</p>

<p>There is a proof of this <a href="http://people.csail.mit.edu/rrw/qbf-nc-journal-rev.pdf" rel="nofollow noreferrer">here</a> on page 6 (see Theorem 3.1 (Folklore)).</p>

CC BY-SA 3.0
2017-04-03T05:10:57.297Z
This is perfect, thanks! And thanks to Ryan!
Izaak Meckler
CC BY-SA 3.0
2017-04-01T20:47:04.467Z
2017-04-06T03:33:14.520Z
2017-04-06T03:33:14.520Z
Dylan McKay
<p>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.</p>

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

<cc.complexity-theory><circuit-complexity><circuit-families>
Small circuits for circuit evaluation problem
Izaak Meckler
# Small circuits for circuit evaluation problem

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

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

**Tags:** cc.complexity-theory, circuit-complexity, circuit-families

---

## 1 answers

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

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](http://people.csail.mit.edu/rrw/qbf-nc-journal-rev.pdf) on page 6 (see Theorem 3.1 (Folklore)).

> **Comments:**
> **username_0**: This is perfect, thanks! And thanks to Ryan!  

---

