<p>The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by:</p>

<ol>
<li>start with an $O(\log{n})$-depth polynomial sized Boolean circuit of fan-in $2$ over $\{\vee, \wedge,\neg\}$ </li>
<li>convert it to a <em>formula</em> (i.e. a circuit where all gates have fan-out bounded by 1) with a polynomial blowup in size and maintaining the depth, </li>
<li>run a stack algorithm with an $O(\log{n})$ depth stack with entries which are bits indicating the values of gates that have been evaluated along a path from current node to the output node</li>
</ol>

<p>Thus the space used is logarithmic in the input completing the proof. Notice, that the entries are single bits because we didn't explicitly need to store the name of the gates along with the value since the circuit is a formula (just storing the name of the current gate suffices since tracing back its ancestor chain and thus the name of the gates whose values we have in the stack, is easy).</p>

<p>In trying to generalize this directly to $NC^i$ circuits ($i &gt; 1$) the second step above does not seem possible (unless the $NC$ hierarchy collapses to $NC^1$). So in order to perform the simulation it seems necessary to remember the name of the gates along the ancestor chain. Notice that instead we could also remember $\log{f}$ bits where $f$ is an upper bound on the <em>fan-out</em> of a gate since this would also uniquely identify the chain of nodes from which the current node is descended from. This impli $NC^i \subseteq DSPACE[\log^{i+1}{n}]$ since the trivial upper bound on $f$ is polynomial.</p>

<p>My question is can we bound $f$ by a constant or through some other means show that $NC^i \subseteq DSPACE[\log^i{n}]$. This <a href="https://cstheory.stackexchange.com/a/190/214">answer</a> seems to indicate that this is indeed the case. I am interested in knowing the reference and/or the proof.</p>

CC BY-SA 3.0
2012-03-08T03:49:00.327Z
The answer is by @Noam and this comment might flag his attention.
Suresh Venkat
CC BY-SA 3.0
2012-03-08T03:50:07.743Z
Isn't it already bounded by the definition of class $\mathsf{NC^i}$? It seems that you are talking about class $\mathsf{AC^i}$.
Kaveh
CC BY-SA 3.0
2012-03-08T04:14:08.510Z
I do not know why you consider the fan-out of a gate.  The fan-in being constant is sufficient for that idea, and that is Lemma 1 of [Borodin SICOMP 1977](http://dx.doi.org/10.1137/0206054).
Tsuyoshi Ito
CC BY-SA 3.0
2013-10-28T18:28:07.537Z
@Tsuyoshi Sorry! It's perhaps too late in the day but your comment points to the correct answer and I will acknowledge it if you convert it to an answer. Thanks.
SamiD
<reference-request><complexity-classes><dc.parallel-comp><space-bounded>
$NC^i \subseteq DSPACE[\log^i{n}]$?
SamiD
# $NC^i \subseteq DSPACE[\log^i{n}]$?

(Asked by: username_0 on 2012-03-08)

The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by:

1. start with an $O(\log{n})$-depth polynomial sized Boolean circuit of fan-in $2$ over $\{\vee, \wedge,\neg\}$
2. convert it to a *formula* (i.e. a circuit where all gates have fan-out bounded by 1) with a polynomial blowup in size and maintaining the depth,
3. run a stack algorithm with an $O(\log{n})$ depth stack with entries which are bits indicating the values of gates that have been evaluated along a path from current node to the output node

Thus the space used is logarithmic in the input completing the proof. Notice, that the entries are single bits because we didn't explicitly need to store the name of the gates along with the value since the circuit is a formula (just storing the name of the current gate suffices since tracing back its ancestor chain and thus the name of the gates whose values we have in the stack, is easy).

In trying to generalize this directly to $NC^i$ circuits ($i > 1$) the second step above does not seem possible (unless the $NC$ hierarchy collapses to $NC^1$). So in order to perform the simulation it seems necessary to remember the name of the gates along the ancestor chain. Notice that instead we could also remember $\log{f}$ bits where $f$ is an upper bound on the *fan-out* of a gate since this would also uniquely identify the chain of nodes from which the current node is descended from. This impli $NC^i \subseteq DSPACE[\log^{i+1}{n}]$ since the trivial upper bound on $f$ is polynomial.

My question is can we bound $f$ by a constant or through some other means show that $NC^i \subseteq DSPACE[\log^i{n}]$. This [answer](https://cstheory.stackexchange.com/a/190/214) seems to indicate that this is indeed the case. I am interested in knowing the reference and/or the proof.

**Tags:** reference-request, complexity-classes, dc.parallel-comp, space-bounded

> **Comments:**
> **username_1**: The answer is by @Noam and this comment might flag his attention.  
> **username_2**: Isn't it already bounded by the definition of class $\mathsf{NC^i}$? It seems that you are talking about class $\mathsf{AC^i}$.  
> **username_3**: I do not know why you consider the fan-out of a gate.  The fan-in being constant is sufficient for that idea, and that is Lemma 1 of [Borodin SICOMP 1977](http://dx.doi.org/10.1137/0206054).  
> **username_0**: @Tsuyoshi Sorry! It's perhaps too late in the day but your comment points to the correct answer and I will acknowledge it if you convert it to an answer. Thanks.  

---

## 0 answers

