Let C={Cn} be a family of uniform boolean circuits, whose size and depth are bounded by functions s(n) and d(n).
What is the upper bound on the running time of a Turing machine M that evaluates C? How tight is this upper bound?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityLet C={Cn} be a family of uniform boolean circuits, whose size and depth are bounded by functions s(n) and d(n).
What is the upper bound on the running time of a Turing machine M that evaluates C? How tight is this upper bound?
I am assuming that we are talking about bounded fan-in circuits.
If a language can be decided by a deterministic Turing machine in time $t_n$ and space $s_n$, then it can be computed by a circuit of size $O(t_n\log s_n)$. The depth can be reduced to $d_n = l_n \log t_n = O(l^2_n)$ where $l_n = \max (s_n,\log n)$.
In the non-uniform circuit case and non-uniform TMs (NU-TM) (when the space used by a TM includes the log of space used on the oracle tape containing the advice), if the language has circuits of size $c_n = \Omega(n)$, then it can be decided by an NU-TM where time $t_n = O(c^2_n)$ and space $s_n = O(c_n)$.
Similarly for depth $d_n = \Omega(\log n)$, we get an NU-TM with time $t_n = O(n2^{d_n})$ and space $s_n = O(d_n)$.
Form these results we get:
I think we can extend this to uniform classes if we use appropriate uniformity conditions on both sides.
See also chapter 9 of Wegener's book "The Complexity of Boolean Functions" for more details.