<p>I am interesting in strict and ``right'' formulations of results about <span class="math-container">$\mathrm{NC}^1$</span>-completeness of some languages.</p>
<p>Consider for example Barrington's theorem about <span class="math-container">$\mathrm{NC}^1$</span>-completeness of the problem of multiplying together a sequence of elements of the permutation group <span class="math-container">$S_5$</span>.</p>
<p>I think that this theorem can be formulated by the following way:</p>
<p><em>This language is complete in the class uniform-<span class="math-container">$\mathrm{NC}^1$</span> under uniform-<span class="math-container">$\mathrm{NC}^0$</span>-reduction.</em></p>
<p>I think that we understand what exactly means uniform-<span class="math-container">$\mathrm{NC}^1$</span>: there are several definitions that are <a href="https://www.sciencedirect.com/science/article/pii/002200009090022D" rel="nofollow noreferrer">equivalent</a>.</p>
<p>But what is the right definition of uniform-<span class="math-container">$\mathrm{NC}^0$</span>-reduction?</p>
<p>By right definition I mean a definition that has standard properties: if <span class="math-container">$A \le B$</span> and <span class="math-container">$B \le C$</span> then <span class="math-container">$A \le C$</span>,
if <span class="math-container">$A \le B$</span> and <span class="math-container">$B \in \mathrm{NC}^1$</span> then <span class="math-container">$A \in \mathrm{NC}^1$</span>.</p>
<p>IMHO my question is very natural and I hope that there is an answer in some books or papers. Could you please give a reference?</p>

CC BY-SA 4.0
2023-12-21T13:09:05.673Z
You may consider DLOGTIME projections.
Emil Jeřábek
CC BY-SA 4.0
2023-12-26T06:19:17.693Z
Why not use the obvious definition? "There exists a uniform family of NC^0 circuits that compute the reduction?"
Or Meir
CC BY-SA 4.0
2023-12-26T19:08:38.090Z
In answer to Or Meir's comment: I think that Alexey Milavonov's question is really asking what you mean, when you say "there exists a uniform family of NC^0 circuits".  That is, what notion of uniformity should one use?  The "obvious" notion (and the notion that I use when I need to refer to "uniform NC^0" is to say that the function that maps 1^n to a description of C_n is computable in Dlogtime-uniform AC^0.  But note that some people would find this inelegant, since AC^0 is much more powerful than NC^0,  But I don't know of a good alternative.  I agree with Emil  Jeřábek: are good..
Eric Allender
CC BY-SA 4.0
2023-12-26T19:20:49.553Z
By the way, the link to [Barrington, Immerman, Straubing] is more about uniformity for SUBCLASSES of NC^1.  The best treatment of the issue of how to define uniform NC^1 that I know is in the textbook by Vollmer.  One really wants uniform NC^1 to be the same as AlternatingTime(O(log n)).  Simply saying "Dlogtime uniformity" doesn't really work, and you need to make use of the "extended connection language" that was defined first by [Ruzzo].  I suggest looking at Vollmer's discussion of this topic.
Eric Allender
CC BY-SA 4.0
2023-12-26T19:26:03.803Z
One final comment, following up on Emil Jeřábek's comment: Immerman's textbook also discusses an even more restrictive notion of reduction: quantifier-free projections.  These are projections that can be expressed by a first-order formula with no quantifiers.  Many "standard" complete problems for various complexity classes are complete even under quantifier-free projections.  But building such projections can sometimes be a pain, and it frequently doesn't seem (to me) to be worth the effort of proving hardness under quantifier-free projections.
Eric Allender
<reference-request><circuit-complexity><circuit-depth><circuit-families>
What is $\mathrm{NC}^0$-uniform reduction
Alexey Milovanov
# What is $\mathrm{NC}^0$-uniform reduction

(Asked by: username_0 on 2023-12-20)

I am interesting in strict and ``right'' formulations of results about $\mathrm{NC}^1$-completeness of some languages.

Consider for example Barrington's theorem about $\mathrm{NC}^1$-completeness of the problem of multiplying together a sequence of elements of the permutation group $S\_5$.

I think that this theorem can be formulated by the following way:

*This language is complete in the class uniform-$\mathrm{NC}^1$ under uniform-$\mathrm{NC}^0$-reduction.*

I think that we understand what exactly means uniform-$\mathrm{NC}^1$: there are several definitions that are [equivalent](https://www.sciencedirect.com/science/article/pii/002200009090022D).

But what is the right definition of uniform-$\mathrm{NC}^0$-reduction?

By right definition I mean a definition that has standard properties: if $A \le B$ and $B \le C$ then $A \le C$,
if $A \le B$ and $B \in \mathrm{NC}^1$ then $A \in \mathrm{NC}^1$.

IMHO my question is very natural and I hope that there is an answer in some books or papers. Could you please give a reference?

**Tags:** reference-request, circuit-complexity, circuit-depth, circuit-families

> **Comments:**
> **username_1**: You may consider DLOGTIME projections.  
> **username_2**: Why not use the obvious definition? "There exists a uniform family of NC^0 circuits that compute the reduction?"  
> **username_3**: In answer to username_2's comment: I think that Alexey Milavonov's question is really asking what you mean, when you say "there exists a uniform family of NC^0 circuits".  That is, what notion of uniformity should one use?  The "obvious" notion (and the notion that I use when I need to refer to "uniform NC^0" is to say that the function that maps 1^n to a description of C_n is computable in Dlogtime-uniform AC^0.  But note that some people would find this inelegant, since AC^0 is much more powerful than NC^0,  But I don't know of a good alternative.  I agree with Emil  Jeřábek: are good..  
> **username_3**: By the way, the link to [Barrington, Immerman, Straubing] is more about uniformity for SUBCLASSES of NC^1.  The best treatment of the issue of how to define uniform NC^1 that I know is in the textbook by Vollmer.  One really wants uniform NC^1 to be the same as AlternatingTime(O(log n)).  Simply saying "Dlogtime uniformity" doesn't really work, and you need to make use of the "extended connection language" that was defined first by [Ruzzo].  I suggest looking at Vollmer's discussion of this topic.  
> **username_3**: One final comment, following up on username_1's comment: Immerman's textbook also discusses an even more restrictive notion of reduction: quantifier-free projections.  These are projections that can be expressed by a first-order formula with no quantifiers.  Many "standard" complete problems for various complexity classes are complete even under quantifier-free projections.  But building such projections can sometimes be a pain, and it frequently doesn't seem (to me) to be worth the effort of proving hardness under quantifier-free projections.  

---

## 0 answers

