<p>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 </p>

<ul>
<li>Emil Jerabek, "<a href="http://www.math.cas.cz/~jerabek/papers/vnc.pdf" rel="noreferrer">On theories of bounded arithmetic for $\mathsf{NC^1}$</a>",  Ann. Pure Appl. Logic 2011</li>
</ul>

CC BY-SA 3.0
2013-10-22T16:34:42.083Z
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
CC BY-SA 3.0
2013-10-22T16:37:48.643Z
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
CC BY-SA 3.0
2013-10-22T19:03:06.497Z
@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
CC BY-SA 3.0
2013-10-22T21:15:17.647Z
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
CC BY-SA 3.0
2013-10-22T06:43:33.610Z
2013-10-22T16:44:25.117Z
2013-10-22T16:44:25.117Z
Iddo Tzameret
<blockquote>
  <p>Is it known if $\mathsf{NC^1}$ circuit evaluation problem is in $\mathsf{NC^1}$? 
  How about $\mathsf{ALogTime}$ (uniform  $\mathsf{NC^1}$)?</p>
</blockquote>

<p>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)$.</p>

<p>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}$?</p>

<p>The <em>extended connection representation</em> of a circuit includes </p>

<ul>
<li>the number of gates in the circuit, </li>
<li>the type of each gate, and </li>
<li>for every gate $g$ and every path $\pi$ in the DAG of the circuit the gate reached from $g$ following path $\pi$.</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2013-10-21T09:55:02.117Z
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 (http://www.math.cas.cz/~jerabek/papers/vnc.pdf).
Iddo Tzameret
CC BY-SA 3.0
2013-10-21T14:26:34.517Z
@IddoTzameret Maybe you should make your comment an answer.
Dai Le
CC BY-SA 3.0
2013-10-21T19:14:57.653Z
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
CC BY-SA 3.0
2013-10-21T23:11:19.783Z
@Igor, good point. I have to think and clarify.
Kaveh
CC BY-SA 3.0
2013-10-22T16:45:21.450Z
@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
<cc.complexity-theory><reference-request><circuit-complexity>
$\mathsf{NC^1}$ circuit evaluation
Kaveh
# $\mathsf{NC^1}$ circuit evaluation

(Asked by: username_0 on 2013-10-19)

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

**Tags:** cc.complexity-theory, reference-request, circuit-complexity
> **Comments:**
> **username_1**: 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 (http://www.math.cas.cz/~jerabek/papers/vnc.pdf).  
> **username_2**: @IddoTzameret Maybe you should make your comment an answer.  
> **username_3**: 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$ ?  
> **username_0**: @Igor, good point. I have to think and clarify.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2013-10-22. Score: 12 | Accepted answer

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

* Emil Jerabek, "[On theories of bounded arithmetic for $\mathsf{NC^1}$](http://www.math.cas.cz/~jerabek/papers/vnc.pdf)", Ann. Pure Appl. Logic 2011

> **Comments:**
> **username_0**: 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_.  
> **username_0**: 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._  
> **username_1**: @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$.  
> **username_0**: 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.  

---

