What can we say about decision problems having a polynomial time algorithm, ie, in $P$? Do they always have polynomial sized circuits (but not circuits of polynomial depth)?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes. $P \subseteq P/\text{poly}$. In particular, every polynomial-time algorithm can be simulated by a family of polynomial-sized circuits: the circuit just emulates the behavior of the algorithm. That this is possible should be pretty clear from the fact that we execute algorithm on CPUs, which are themselves complex circuits built of gates, so it's perhaps not surprising that you can emulate the algorithm in a circuit whose size is not too much larger than the running time of the algorithm. See, e.g., Why does a polynomial-time language have a polynomial-sized circuit?, https://cstheory.stackexchange.com/q/6721/5038, Why isn't P and P/poly trivially the same?, https://en.wikipedia.org/wiki/P/poly, How to relate circuit size to the running time of Turing machine.
