Can polynomial depth circuits (with, let's say AND, OR, and NOT gates) be simulated in polynomial time?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
