En la teoría de la complejidad computacional , L / poly es la clase de complejidad de las máquinas espaciales logarítmicas con una cantidad polinomial de consejos . L / poli es una clase espacial logarítmica no uniforme , análoga a la clase de tiempo polinomial no uniforme P / poli . [1]
Formalmente, para que un lenguaje formal L pertenezca a L / poly, debe existir una función de aviso f que mapee un entero n a una cadena de polinomio de longitud en n , y una máquina de Turing M con dos cintas de entrada de solo lectura y una de lectura -escribir una cinta de tamaño logarítmico en el tamaño de entrada, de modo que una entrada x de longitud n pertenezca a L si y solo si la máquina M acepta la entrada x , f ( n ) . [2] Alternativamente y de manera más simple, L está en L / poli si y solo si puede ser reconocido porprogramas de ramificación de tamaño polinomial. [3] Una dirección de la prueba de que estos dos modelos de cálculo son equivalentes en potencia es la observación de que, si existe un programa de ramificación de tamaño polinomial, puede ser especificado por la función de asesoramiento y simulado por la máquina de Turing. En la otra dirección, una máquina de Turing con espacio de escritura logarítmico y una cinta de aviso polinomial puede simularse mediante un programa de ramificación cuyos estados representan la combinación de la configuración de la cinta de escritura y la posición de los cabezales de la máquina de Turing en los otros dos. cintas.
En 1979, Aleliunas et al. mostró que el espacio logarítmico simétrico está contenido en L / poly. [4] Sin embargo, este resultado fue reemplazado por el resultado de Omer Reingold de que SL colapsa a un espacio de registro uniforme. [5]
BPL está contenido en L / poly, que es una variante del teorema de Adleman . [6]
Referencias
- ^ Zoológico de complejidad : L / poli .
- ^ Thierauf, Thomas (2000), La complejidad computacional de los problemas de equivalencia e isomorfismo , Notas de conferencias en Ciencias de la Computación, 1852 , Springer-Verlag, p. 66, ISBN 978-3-540-41032-4.
- ^ Cobham, Alan (1966), "El problema de reconocimiento para el conjunto de cuadrados perfectos", Actas del 7mo Simposio Anual del IEEE sobre Teoría de la Conmutación y Autómatas (SWAT 1966) , págs. 78-87, doi : 10.1109 / SWAT.1966.30.
- ^ Aleliunas, Romas; Karp, Richard M .; Lipton, Richard J .; Lovász, László ; Rackoff, Charles (1979), "Caminatas al azar, secuencias transversales universales y la complejidad de los problemas del laberinto", Actas del 20º Simposio Anual sobre Fundamentos de la Ciencia de la Computación , Nueva York: IEEE, págs. 218-223, doi : 10.1109 / SFCS .1979.34 , MR 0598110.
- ^ Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro", Journal of the ACM , 55 (4): 1–24, doi : 10.1145 / 1391289.1391291 , MR 2445014.
- ^ Nisan, Noam (1993), "On read-once vs. multiple access to randomness in logspace", Theoretical Computer Science , 107 (1): 135-144, doi : 10.1016 / 0304-3975 (93) 90258-U , MR 1201169.