# A notion of time for uniform circuits

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?

• Obviously it depends on the time required to generate the circuits, not only s(n) and d(n). May 25 '11 at 3:27
• There's a trivial upper bound of s(n)* d(n) for any particular circuit. It seems to me that requiring uniformity gets you into Tsuyoshi's realm, and it might have been easier to stay nonuniform. May 25 '11 at 5:56
• The question isn't well-posed. Does the Turing machine $M$ get $C$ as input? Or does $M$ have to construct $C$ for itself? If so, what are the resource requirements on constructing $C$? Being "uniform" can mean a lot of things. May 27 '11 at 8:59

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:

• $Size(T^{O(1)}) = NU\text{-}Time(T^{O(1)})$ if $T(n) = \Omega(n)$,
• $Depth(S^{O(1)}) = NU\text{-}Space(S^{O(1)})$ if $S(n) = \Omega(\log n)$.

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.

• It does not answer the question completely but we can derive some lowerbounds from these results. May 27 '11 at 4:13