3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ You need to store intermediate results. If a gate has $m$ inputs, you need to store $m-1$ intermediate results. The fan-in $m$ could be as large as polynomial in $n$. $\endgroup$
    – Yuval Filmus
    Apr 20, 2018 at 20:24
  • $\begingroup$ @YuvalFilmus But you don't. If it's an AND gate, you need only store AND of everything so far. If it's OR, you need only store OR of everything so far. It requires just one bit. $\endgroup$
    – Caleb Stanford
    Apr 20, 2018 at 20:28
  • 2
    $\begingroup$ You have to store your current location in DFS. If instead of a circuit you had a formula, then it suffices just to store the address of one gate, but for a circuit this doesn't seem to work. $\endgroup$
    – Yuval Filmus
    Apr 20, 2018 at 20:33
  • $\begingroup$ Aha, thanks -- I think your last comment may have pointed out the mistake. I was thinking to store the entire path of pointers which obviously doesn't work because that's $\log (n)^2$. Similarly, storing for each node in the DFS an index $i$ which indicates the child gate number would be $\log(n)^2$. $\endgroup$
    – Caleb Stanford
    Apr 20, 2018 at 20:36
  • $\begingroup$ In NC1 you only have to store $i=1$ or $i=2$, so it's constant rather than logspace for each node in the DFS recursion stack. $\endgroup$
    – Caleb Stanford
    Apr 20, 2018 at 20:37

1 Answer 1

Reset to default
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the help, and the proof that $NL \subseteq AC^1$. $\endgroup$
    – Caleb Stanford
    Apr 20, 2018 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.