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?
$\begingroup$
$\endgroup$
-
4$\begingroup$ Obviously it depends on the time required to generate the circuits, not only s(n) and d(n). $\endgroup$ – Tsuyoshi Ito 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$ – Suresh Venkat 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$ – Ryan Williams May 27 '11 at 8:59
$\begingroup$
$\endgroup$
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
