Confusing on the proof $\textbf{NC}^1\subseteq \textbf{L}$ using DFS

Question

On page 430 of Sisper's TOC, Theorem 10.39 proves $\textbf{NC}^1\subseteq \textbf{L}$:

PROOF: We sketch a log space algorithm to decide a language $A$ in $\textbf{NC}^1$ . On input $w$ of length $n$, the algorithm can construct the description as needed of the nth circuit in the uniform circuit family for $A$. Then the algorithm can evaluate the circuit by using a depth-first search from the output gate. Memory for this search is needed only to record the path to the currently explored gate, and to record any partial results that have been obtained along that path. The circuit has logarithmic depth; hence only logarithmic space is required by the simulation.

In my opinion, the algorithm would evaluate values of all gates via DFS, i.e. record the path and its partial results, then check the output gate. However, if we record the path to the currently explored gate, we will need the ID of each gate on the path. There are $n^k$ gates in the $n$th circuit, so we have $O(\log n)$ space to save each ID. Totally, the algorithm bears $O(\log^2n)$ space for the algorithm because of $O(\log n)$ depth.

I know that the proof is being taught in many lectures so far, it is probably correct but what have I missed?

Answer 1

You do not record the path as a sequence of node IDs. You only record for each node the 1-bit information whether you continued from that node left or right, and you keep a pointer to the last node of the path. This takes space $O(\log n)$. When you need to backtrack, you recompute the pointer to the parent node by starting at the root and following the recorded sequence of left-or-right turns.

• minh quý lê: I thought using singly linked list in my mind. It should be utilized a variant of doubly linked list to represent the circuits, shouldn't it? A child points to its parent and the parent points to its at most 2 children.
• Emil Jeřábek: You do not use any lists. That’s the point. In order to make the space usage only $O(]log n),ドル you only write the sequence of bits.
• minh quý lê: I mean the generating logspace algorithm use doubly linked list to represent/output the circuits. Thus we can utilize that fact and 0, 1 bits to maintain the path. Sorry for my English!
• Emil Jeřábek: Oh, you mean the input is a doubly linked list. I don’t see how that would be possible, unless the circuit is a formula (i.e., tree-like). Otherwise, a node does not have a uniquely defined parent. But anyway, it is not needed.
• minh quý lê: Yes, a tree-like data structure is more reasonable. Moreover, each node should be maintain pointer to its parent as well as its 2 children, right? That two-way approach makes us easy to do DFS.