patternMinor
Is it known that $AC^1 \subseteq L$?
Viewed 0 times
subseteqthatknown
Problem
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?
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?
Solution
Matrix powering shows that directed reachability is in $\mathsf{AC^1}$, and so $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC^1}$. In more detail, suppose that $A$ is the adjacency matrix of a directed graph $G$, with self-loops on all vertices. The matrix $B_{ij} = \bigvee_k A_{ik} \land A_{kj}$, which can be computed in $\mathsf{AC^0}$, is the adjacency matrix of $G^2$. In other words, $B_{ij} = 1$ iff there is a path of length at most 2 from $i$ to $j$ in $G$. Iterating this construction $\log n$ times, we obtain an $\mathsf{AC^1}$ circuit computing the adjacency matrix of $G$, that is, which vertex is reachable from which vertex.
What goes wrong when using DFS to evaluate $\mathsf{AC^1}$ circuits? The same approach works, only it uses $\log^2 n$ space rather than $\log n$ space. The reason is that at each level, you need $\log n$ space to store which child you are currently in. Multiplied by the number of levels, we obtain $\log^2 n$.
What goes wrong when using DFS to evaluate $\mathsf{AC^1}$ circuits? The same approach works, only it uses $\log^2 n$ space rather than $\log n$ space. The reason is that at each level, you need $\log n$ space to store which child you are currently in. Multiplied by the number of levels, we obtain $\log^2 n$.
Context
StackExchange Computer Science Q#90948, answer score: 4
Revisions (0)
No revisions yet.