Editing NC (complexity) (section)

=== Uniformity ===
There are various levels of uniformity being considered. A family of boolean circuits is uniform if the schematics for any member of the family can be produced by a Turing machine under various resource constraints. With different levels of constraints, we would obtain possibly different complexity classes, with a more stringent constraint leading to a possibly smaller complexity class.

In the literature, the following uniformities have been considered for the '''NC'''<sup>''1''</sup> class, arranged according to strength:<ref name=":0" />{{Pg|page=139}}<ref>{{Cite journal |last1=Mix Barrington |first1=David A. |last2=Immerman |first2=Neil |last3=Straubing |first3=Howard |date=1990-12-01 |title=On uniformity within NC1 |url=https://dx.doi.org/10.1016/0022-0000%2890%2990022-D |journal=Journal of Computer and System Sciences |volume=41 |issue=3 |pages=274–306 |doi=10.1016/0022-0000(90)90022-D |issn=0022-0000}}</ref>

* '''NC'''<sup>''1''</sup> itself. This is also called the <math>U_{E^*}</math>-uniformity. It is equivalent to [[Alternating Turing machine|'''ALOGTIME''']].
* '''LOGSPACE'''.
* '''P'''.
* '''Computable'''. Any halting Turing machine is allowed.
* '''Non-uniform'''. This is the strongest case. The boolean circuit family may contain arbitrary elements of the correct width and depth, even if the family cannot be generated by any algorithm.
By default, the literature uses '''LOGSPACE''' uniformity.

Because it is possible that <math>\mathsf{NC}^1 \subsetneq \mathsf{LOGSPACE}</math>, researchers may use '''NC'''<sup>''1''</sup>-uniformity, since it is a possible strengthening. To avoid self-reference, '''NC'''<sup>''1''</sup>-uniform '''NC'''<sup>''1''</sup> is defined as follows: A '''NC'''<sup>''1''</sup> Boolean circuit family is '''NC'''<sup>''1''</sup>-uniform if the set of descriptions is decided by an '''ALOGTIME''' [[alternating Turing machine]]. The machine reads in a length-<math>n</math> description of a Boolean circuit, and halts in time <math>O(\log n)</math>.<ref name=":0" />{{Pg|page=139}}

For higher classes '''NC'''<sup>''2''</sup>, '''NC'''<sup>''3''</sup>, ..., there are similar uniformities definable. However, for <math>k \geq 2</math>, '''NC'''<sup>''k''</sup>-uniform '''NC'''<sup>''k''</sup> and '''LOGSPACE'''-uniform '''NC'''<sup>''k''</sup> are equal, and both are equivalent to the following definition: The family is decided by an [[alternating Turing machine]]. The machine reads in a length-<math>n</math> description of a Boolean circuit, and halts in time <math>O((\log n)^k)</math> and space <math>O(\log n)</math>.<ref name=":0" />{{Pg|page=139}}