<p>I am assuming that we are talking about bounded fan-in circuits. </p>

<p>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)$.</p>

<p>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)$.</p>

<p>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)$.</p>

<p>Form these results we get:</p>

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

<p>I think we can extend this to uniform classes if we use appropriate uniformity conditions on both sides.</p>

<p>See also chapter 9 of Wegener's book "The Complexity of Boolean Functions" for more details.</p>

CC BY-SA 3.0
2011-05-27T04:13:40.740Z
It does not answer the question completely but we can derive some lowerbounds from these results.
Kaveh
CC BY-SA 3.0
2011-05-27T04:12:01.287Z
2011-05-27T04:12:01.287Z
Kaveh
<p>Let C={C<sub>n</sub>} be a family of <strong>uniform</strong> boolean circuits, whose size and depth are bounded by functions s(n) and d(n).</p>

<p>What is the upper bound on the running time of a Turing machine M that evaluates C? How tight is this upper bound?</p>

CC BY-SA 3.0
2011-05-25T03:27:40.883Z
Obviously it depends on the time required to generate the circuits, not only s(n) and d(n).
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-25T05:56:25.470Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-05-27T08:59:43.660Z
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.
Ryan Williams
<cc.complexity-theory><turing-machines><circuit-complexity><time-complexity>
A notion of time for uniform circuits
Incredible
# A notion of time for uniform circuits

(Asked by: username_0 on 2011-05-25)

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?

**Tags:** cc.complexity-theory, turing-machines, circuit-complexity, time-complexity

> **Comments:**
> **username_1**: Obviously it depends on the time required to generate the circuits, not only s(n) and d(n).  
> **username_2**: 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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2011-05-27. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_4**: It does not answer the question completely but we can derive some lowerbounds from these results.  

---

