1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

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.