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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.