# What is $\mathrm{NC}^0$-uniform reduction

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.

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?

• You may consider DLOGTIME projections. Dec 21, 2023 at 13:09
• Why not use the obvious definition? "There exists a uniform family of NC^0 circuits that compute the reduction?" Dec 26, 2023 at 6:19
• 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.. Dec 26, 2023 at 19:08
• 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. Dec 26, 2023 at 19:20
• 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. Dec 26, 2023 at 19:26