# Size, depth, and time of circuits

Can polynomial depth circuits (with, let's say AND, OR, and NOT gates) be simulated in polynomial time?

## 1 Answer

No. Every function can be implemented with a polynomial-depth circuit, but not all function families can be implemented with a polynomial-time algorithm.

In particular, if we're allowed unbounded fan-in/fan-out, you can implement every function in depth 2 using a CNF or DNF formula for the function (but the size of the circuit is exponential). If we're only allowed constant fan-in/fan-out, you can simulate that with linear depth (use a $$n$$-layer tree to make exponentially many copies of each input; then 1 layer to evaluate the CNF clauses; then a $$n$$-layer AND tree).