3
$\begingroup$

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 seems to indicate that this is indeed the case. I am interested in knowing the reference and/or the proof.

$\endgroup$
  • 2
    $\begingroup$ The answer is by @Noam and this comment might flag his attention. $\endgroup$ – Suresh Venkat Mar 8 '12 at 3:49
  • 1
    $\begingroup$ Isn't it already bounded by the definition of class $\mathsf{NC^i}$? It seems that you are talking about class $\mathsf{AC^i}$. $\endgroup$ – Kaveh Mar 8 '12 at 3:50
  • 3
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 8 '12 at 4:14
  • $\begingroup$ @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. $\endgroup$ – SamiD Oct 28 '13 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.