# $\mathsf{NC^1}$ circuit evaluation

Is it known if $\mathsf{NC^1}$ circuit evaluation problem is in $\mathsf{NC^1}$? How about $\mathsf{ALogTime}$ (uniform $\mathsf{NC^1}$)?

We know that circuits of depth $k$ can be evaluated with circuits of depth $k+c$ where $c$ is a universal constant. This means circuits of depth $k\lg n + o(\lg n)$ can be evaluated by a circuit of depth $O(\lg n)$. However $O(\lg n)$ doesn't contain a function that eventually dominates all functions in $O(\lg n)$.

We know that formula evaluation problem is in $\mathsf{ALogTime}$. Every $\mathsf{NC^1}$ circuit is equivalent to a Boolean formula. Can't we compute the extended connection representation of an equivalent Boolean formula from that of a given $\mathsf{NC^1}$ circuit in $\mathsf{ALogTime}$?

The extended connection representation of a circuit includes

• the number of gates in the circuit,
• the type of each gate, and
• for every gate $g$ and every path $\pi$ in the DAG of the circuit the gate reached from $g$ following path $\pi$.

A path is given by a 0/1 sequence where 0 represents moving to the left parent and 1 represents moving to the right parent. Note that the number of paths is polynomial: the length of the paths is bounded by the depth of the circuit.

• As far as I know, $NC^1$ evaluation is not known to be in $NC^1$, and is conjectured to be outside $NC^1$. See "On theories of bounded arithmetic for $NC^1$", E. Jerabek, Ann. Pure Appl. Logic 2011 (math.cas.cz/~jerabek/papers/vnc.pdf). – Iddo Tzameret Oct 21 '13 at 9:55
• @IddoTzameret Maybe you should make your comment an answer. – Dai Le Oct 21 '13 at 14:26
• What do you mean by NC1-circuit evaluation? Do you mean that the input given to the evaluator is a circuit $C$ whose depth is bounded by $c\log(n)$ for some fixed constant $c$, where $n$ is the number of inputs to $C$ ? – Igor Shinkar Oct 21 '13 at 19:14
• @Igor, good point. I have to think and clarify. – Kaveh Oct 21 '13 at 23:11
• @igor, I think we can assume the depth of the circuit is $c \lg n$ for some arbitrary but fixed constant $c\geq 1$ as that is hard for $\mathsf{NC^1}$ under $\mathsf{AC^0}$ reductions. – Kaveh Oct 22 '13 at 16:45

As far as I know, $\mathsf{NC^1}$ evaluation is not known to be in $\mathsf{NC^1}$, and is conjectured to be outside $\mathsf{NC^1}$. See
• Thanks Iddo. I am looking at Emil's paper and it is very helpful. He states that the problem is not known to be in $\mathsf{NC^1}$ if we use direct connection representation but it is in $\mathsf{NC^1}$ if we use extended connection representation. – Kaveh Oct 22 '13 at 16:34
• He goes on to state that the following problem is the core difficulty of computing $\mathsf{NC^1}$ circuit evaluation (with d.c. representation): Given a directed graph $G$ on $n$ vertices with bounded out-degree, vertices $x,y \in G$, and a number $d \leq \log n$, determine whether $y$ is reachable from $x$ in at most $d$ steps. – Kaveh Oct 22 '13 at 16:37
• @Kaveh, you can also look at "Amplifying Lower Bounds by Means of Self-Reducibility" by Allender and Koucky (JACM 2010). They also state the $NC^1$ evaluation problem not to be known in $NC^1$. – Iddo Tzameret Oct 22 '13 at 19:03
• Actually that line was the inspiration for my question. I felt it should be in $\mathsf{NC^1}$ if we use extended connection representation and Emil's paper states that it is indeed. – Kaveh Oct 22 '13 at 21:15