<p>I don't have much intuition about non-uniformity so the question may be quite naive.</p>

CC BY-SA 4.0
2024-05-28T10:06:55.397Z
The question is quite vague; it’s not very clear what kind of an answer you expect. You can consider L-completeness under nonuniform $\let\R\mathrm\R{AC}^0$-reductions, why not? It’s sure better than nothing. Yes, it shows unconditionally that $A$ is not in nonuniform $\R{AC}^0$, or even $\R{AC}^0[p]$ for prime $p$, and conditionally, that $A$ is not in nonuniform $\R{NC^1}$. [I don’t see why you want “logspace-uniform $\R{NC^1}$”, as this is weaker than the usual notion of uniform $\R{NC^1}$ (which is $U_E$-uniform). Anyway, it shows nothing more for uniform $\R{NC^1}$ than for nonuniform.]
Emil Jeřábek
CC BY-SA 4.0
2024-05-28T12:44:52.970Z
Thank you, @EmilJeřábek!

Which condition is needed to say that A is not in non-uniform $NC^1$? Just that $NC^1$ is not equal to $L$?
[I mentioned logspace-uniformness because this is what I read in textbooks, I didn't even know what $U_E$ was :)]
A. G.
CC BY-SA 4.0
2024-05-28T13:02:37.947Z
You need L not to be included in nonuniform NC^1 for this to imply a separation. If a textbook suggested to use logspace uniformity for NC^1, toss it out. You cannot get a decent definition of a uniform class by using a uniformity that by itself has a greater computational power than the circuit notion to which you want to apply it. The appropriate notion of uniformity for classes below L (such as AC^0, TC^0, or NC^1) is DLOGTIME uniformity. The only catch is that in order to get the right definition of uniform NC^1, the uniformity needs to describe the extended connection language of the ...
Emil Jeřábek
CC BY-SA 4.0
2024-05-28T13:07:04.800Z
... circuit family rather than the, perhaps more intuitive, direct connection language. The two versions of DLOGTIME uniformity using d.c.l. and e.c.l. are called U_D-uniformity and U_E-uniformity; see Barrington, Immerman, Straubing, *On uniformity within NC^1*, for details (the notions of dcl, ecl, and U_D and D_E uniformity come originally from Ruzzo, *On uniform circuit complexity*). Uniform NC^1 can be also defined without using any circuits and uniformities at all as ALOGTIME.
Emil Jeřábek
CC BY-SA 4.0
2024-05-28T14:11:46.113Z
Thank you! It's much clearer now
A. G.
<circuit-complexity><reductions><logspace><advice-and-nonuniformity><ac0>
Is a problem, that is $L$-complete under non-uniform $AC^0$ reductions, necessarily outside of (non-uniform or uniform) $NC^1$?
A. G.
# Is a problem, that is $L$-complete under non-uniform $AC^0$ reductions, necessarily outside of (non-uniform or uniform) $NC^1$?

(Asked by: username_0 on 2024-05-28)

I don't have much intuition about non-uniformity so the question may be quite naive.

**Tags:** circuit-complexity, reductions, logspace, advice-and-nonuniformity, ac0
> **Comments:**
> **username_1**: The question is quite vague; it’s not very clear what kind of an answer you expect. You can consider L-completeness under nonuniform $\let\R\mathrm\R{AC}^0$-reductions, why not? It’s sure better than nothing. Yes, it shows unconditionally that $A$ is not in nonuniform $\R{AC}^0$, or even $\R{AC}^0[p]$ for prime $p$, and conditionally, that $A$ is not in nonuniform $\R{NC^1}$. [I don’t see why you want “logspace-uniform $\R{NC^1}$”, as this is weaker than the usual notion of uniform $\R{NC^1}$ (which is $U_E$-uniform). Anyway, it shows nothing more for uniform $\R{NC^1}$ than for nonuniform.]  
> **username_0**: Thank you, @EmilJeřábek!  Which condition is needed to say that A is not in non-uniform $NC^1$? Just that $NC^1$ is not equal to $L$? [I mentioned logspace-uniformness because this is what I read in textbooks, I didn't even know what $U_E$ was :)]  
> **username_1**: You need L not to be included in nonuniform NC^1 for this to imply a separation. If a textbook suggested to use logspace uniformity for NC^1, toss it out. You cannot get a decent definition of a uniform class by using a uniformity that by itself has a greater computational power than the circuit notion to which you want to apply it. The appropriate notion of uniformity for classes below L (such as AC^0, TC^0, or NC^1) is DLOGTIME uniformity. The only catch is that in order to get the right definition of uniform NC^1, the uniformity needs to describe the extended connection language of the ...  
> **username_1**: ... circuit family rather than the, perhaps more intuitive, direct connection language. The two versions of DLOGTIME uniformity using d.c.l. and e.c.l. are called U_D-uniformity and U_E-uniformity; see Barrington, Immerman, Straubing, *On uniformity within NC^1*, for details (the notions of dcl, ecl, and U_D and D_E uniformity come originally from Ruzzo, *On uniform circuit complexity*). Uniform NC^1 can be also defined without using any circuits and uniformities at all as ALOGTIME.  
> **username_0**: Thank you! It's much clearer now  

---

## 0 answers

