Condición de uniformidad "correcta" para la clase de Nick

DLOGTIME se define en http://en.wikipedia.org/wiki/DLOGTIME
se define en http://en.wikipedia.org/wiki/L_%28complexity%29 NC y NC n se definen en http: // en .wikipedia.org / wiki / NC_% 28complexity% 29$\operatorname{L}$
$\operatorname{NC}$$\operatorname{NC}^n$

DLOGTIME parece ser el más pequeño que podría funcionar.
He leído en varios lugares que$\, \operatorname{L} \subseteq \operatorname{NC}^2 \,$, $\,$aunque en todos los lugares en los que he
encontrado ese resultado que indica una condición de uniformidad usa la uniformidad ¿Hay alguna clase determinista X tal que$\operatorname{L}$


$X$$\, \operatorname{L} \subseteq \operatorname{NC} \,$se conoce con -uniforme NC , y 1.$X$$\operatorname{NC}$
$\;$ ... $\; X\subset \operatorname{L} \;$se sabe que aguanta?
2)$\;$ ... $\; X\subseteq \operatorname{L} \;$ es conocido por sostener y $\, X = \operatorname{L} \,$ no se sabe que aguanta?

(1, o en mucho menor medida 2, parece implicar que la uniformidad es la condición correcta)$\operatorname{L}$

Puede usar para la uniformidad de N C y N C 2 . No hay problema y las clases uniformes N C k permanecen iguales e iguales a A T i m e S p a c e ( O ( lg k n ) , O ( lg n ) ) (para k ≥ 1 ).$\mathsf{DLogTime}$$\mathsf{NC}$$\mathsf{NC^2}$$\mathsf{NC^k}$$\mathsf{ATimeSpace}(O(\lg^k n),O(\lg n))$$k\geq1$

En general, el único caso en el que debemos ser más cuidadosos es el caso , en el que se debe tener cuidado con lo que debe ser decidible en D L o g T i m e . Si utiliza la descripción extendida del lenguaje de conexión de los circuitos, todo funciona incluso en el caso N C 1 .$\mathsf{NC^1}$$\mathsf{DLogTime}$$\mathsf{NC^1}$

Para más información sobre uniformidad ver:

Walter L. Ruzzo, " Sobre la complejidad del circuito uniforme ", Journal of Computer and System Sciences, vol. 22 (1981), págs. 365-383.