¿Tiene L una definición en términos de circuitos?

Muchas clases de complejidad definidas con máquinas de Turing tienen definiciones en términos de circuitos uniformes. Por ejemplo, P también se puede definir usando circuitos de tamaño polinómico uniforme, y de manera similar BPP, NP, BQP, etc. se pueden definir con circuitos uniformes.

Entonces, ¿hay una definición de L basada en un circuito?

Una idea obvia sería permitir circuitos de tamaño polinómico con alguna limitación de profundidad, pero esto resulta para definir la jerarquía NC.

Estaba pensando en esta pregunta hace mucho tiempo, pero no encontré una respuesta. Si no recuerdo mal, mi motivación fue entender cómo se vería el análogo cuántico de L.

cc.complexity-theory complexity-classes circuit-complexity Robin Kothari
fuente

¿Los circuitos de tamaño logarítmico contienen

L

$L$

Mohammad Al-Turkistany

@Turkistany: No, no lo creo, ya que un circuito de tamaño de registro puede tener, como máximo, profundidad de registro y, por lo tanto, está contenido en NC_1, que se define como profundidad de registro, circuitos de tamaño de polietileno. NC_1 está contenido en L, y no se sabe que sea igual a L.

Robin Kothari

Respuestas:

Bueno, , donde es la clase de lenguajes calculados por circuitos de tamaño polinomial de ancho . $L = SC^1$ $SC^1$ $O(\log n)$

En cuanto a , podría caracterizarse como los lenguajes de clase calculados por circuitos de inclinación de tamaño polinómico (que en cierto sentido es solo otra forma de decir programas de ramificación no deterministas). $NL$

Kristoffer Arnsfelt Hansen
fuente

Necesitamos que los circuitos sean uniformes, ¿verdad?

Hsien-Chih Chang 張顯之

Correcto, deben ser uniformes.

Kristoffer Arnsfelt Hansen

S C^{1}

$SC^1$

D T i m e S p a c e (p o l y, l o g)

$DTimeSpace(poly,log)$

@KristofferArnsfeltHansen: Ha pasado un tiempo desde que respondiste esto, pero ¿tienes una referencia donde se pruebe la equivalencia entre el circuito y las definiciones TM de L?

Robin Kothari

@ Robin, no puedo pensar en eso, en realidad. ¿Quizás Vinay lo sabe?

Kristoffer Arnsfelt Hansen

$NC^1$ $LOGCFL$ $L$ $LOGDCFL$ $L = MWidth, Size(log,poly).$

$NL$ $NL$

V Vinay
fuente