Question

A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ circuit and do depth-first-search on the output gate of the circuit. Recursively evaluating the gates in the circuit works because the depth of recursion never goes beyond the depth of the circuit, which is $\log n$.

My question: doesn't the same argument show that $AC^1 \subseteq L$? In this case, with unbounded fan-in, we have to modify the argument slightly, to make sure we are only storing, at each gate, a pointer to the current input gate we are recursing on, and the result (AND or OR) of all input gates up to this point. But it should still be $\log n$.

There must be something wrong with this argument, since I don't see $AC^1 \subseteq L$ referenced anywhere, and the Complexity Zoology inclusion diagram does not list $AC^1$ as a subset of $L$ :( So, what is the error in my thinking?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top