<p>I want to know what the actual difference between the uniformity conditions for NC¹ is. I know that for <span class="math-container">$k\geq 2$</span> <span class="math-container">$NC^k$</span> the uniformity conditions are equivalent, but for NC¹ they are not.</p>
<p>I am wondering why that is? Is there anything that a <span class="math-container">$U_B$</span>-uniform <span class="math-container">$NC¹$</span> Circuit family can compute but not a <span class="math-container">$U_E$</span>-Uniform <span class="math-container">$NC¹$</span> Circuit family? Or is it simply not know if the different uniformity conditions are also equivalent for NC¹?</p>

CC BY-SA 4.0
2024-03-07T05:41:37.937Z
Do you mean $U_D$ rather than $U_B$?
Emil Jeřábek
CC BY-SA 4.0
2024-03-07T08:14:39.983Z
In contrast to e.c.l., a universal evaluator for $\mathrm{NC}^1$-circuits described by d.c.l.  (given a d.c.l. of a log-depth variable-free circuit, output the value of the circuit) does not seem to be in $\mathrm{NC}^1$; it is $\mathrm{NC}^1$-Turing equivalent to the problem denoted by $\mathrm{REACH}_1(\log n)$ in Allender and Barrington, *Uniform circuits for division: consequences and problems*: given a digraph of out-degree 1 (or: bounded out-degree), vertices $x,y$, and $d\le\log n$, determine if $y$ is reachable from $x$ in $d$ steps. See Proposition 2.1 in my paper *On theories of* ...
Emil Jeřábek
CC BY-SA 4.0
2024-03-07T08:17:07.003Z
... *bounded arithmetic for $NC^1$*. However, this does not actually answer the question, as the d.c.l. universal evaluator is not known to be in $U_D$-uniform (or even nonuniform) $\mathrm{NC^1}$ either.
Emil Jeřábek
CC BY-SA 4.0
2024-03-07T08:19:41.063Z
Another nonexample is the AKS sorting network, which gives $U_D$-uniform monotone $\mathrm{NC^1}$-circuits, but there does not seem to be a way of making them $U_E$-uniform. However, the language computed by these circuits (Majority) of course has $U_E$-uniform *nonmonotone* $\mathrm{NC^1}$-circuits.
Emil Jeřábek
<circuit-complexity><uniformity>
What is the actual difference between uniformity conditions for NC¹
lzrdnb
# What is the actual difference between uniformity conditions for NC¹

(Asked by: username_0 on 2024-03-06)

I want to know what the actual difference between the uniformity conditions for NC¹ is. I know that for $k\geq 2$ $NC^k$ the uniformity conditions are equivalent, but for NC¹ they are not.

I am wondering why that is? Is there anything that a $U\_B$-uniform $NC¹$ Circuit family can compute but not a $U\_E$-Uniform $NC¹$ Circuit family? Or is it simply not know if the different uniformity conditions are also equivalent for NC¹?

**Tags:** circuit-complexity, uniformity
> **Comments:**
> **username_1**: Do you mean $U_D$ rather than $U_B$?  
> **username_1**: In contrast to e.c.l., a universal evaluator for $\mathrm{NC}^1$-circuits described by d.c.l.  (given a d.c.l. of a log-depth variable-free circuit, output the value of the circuit) does not seem to be in $\mathrm{NC}^1$; it is $\mathrm{NC}^1$-Turing equivalent to the problem denoted by $\mathrm{REACH}_1(\log n)$ in Allender and Barrington, *Uniform circuits for division: consequences and problems*: given a digraph of out-degree 1 (or: bounded out-degree), vertices $x,y$, and $d\le\log n$, determine if $y$ is reachable from $x$ in $d$ steps. See Proposition 2.1 in my paper *On theories of* ...  
> **username_1**: ... *bounded arithmetic for $NC^1$*. However, this does not actually answer the question, as the d.c.l. universal evaluator is not known to be in $U_D$-uniform (or even nonuniform) $\mathrm{NC^1}$ either.  
> **username_1**: Another nonexample is the AKS sorting network, which gives $U_D$-uniform monotone $\mathrm{NC^1}$-circuits, but there does not seem to be a way of making them $U_E$-uniform. However, the language computed by these circuits (Majority) of course has $U_E$-uniform *nonmonotone* $\mathrm{NC^1}$-circuits.  

---

## 0 answers

