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?

  • 4
    $\begingroup$ Obviously it depends on the time required to generate the circuits, not only s(n) and d(n). $\endgroup$ May 25 '11 at 3:27
  • 2
    $\begingroup$ 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. $\endgroup$ May 25 '11 at 5:56
  • 1
    $\begingroup$ 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. $\endgroup$ 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.

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

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.