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

Improve this question
$\endgroup$
5
  • 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, 2013 at 9:55
  • 1
    $\begingroup$ @IddoTzameret Maybe you should make your comment an answer. $\endgroup$
    – Dai Le
    Oct 21, 2013 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, 2013 at 19:14
  • $\begingroup$ @Igor, good point. I have to think and clarify. $\endgroup$
    – Kaveh
    Oct 21, 2013 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, 2013 at 16:45

1 Answer 1

Reset to default
12
$\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

Improve this answer
$\endgroup$
4
  • 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, 2013 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, 2013 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, 2013 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, 2013 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.