13
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ 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). $\endgroup$ – Iddo Tzameret Oct 21 '13 at 9:55
  • 1
    $\begingroup$ @IddoTzameret Maybe you should make your comment an answer. $\endgroup$ – Dai Le Oct 21 '13 at 14:26
  • 2
    $\begingroup$ 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$ ? $\endgroup$ – Igor Shinkar Oct 21 '13 at 19:14
  • $\begingroup$ @Igor, good point. I have to think and clarify. $\endgroup$ – Kaveh Oct 21 '13 at 23:11
  • $\begingroup$ @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. $\endgroup$ – Kaveh Oct 22 '13 at 16:45
11
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Oct 22 '13 at 16:34
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 22 '13 at 16:37
  • 1
    $\begingroup$ @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$. $\endgroup$ – Iddo Tzameret Oct 22 '13 at 19:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Oct 22 '13 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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