Asesoramiento (complejidad)
En la teoría de la complejidad computacional , una cadena de consejos es una entrada adicional a una máquina de Turing que puede depender de la longitud n de la entrada, pero no de la entrada en sí. Un problema de decisión está en la clase de complejidad P / f ( n ) si hay una máquina de Turing de tiempo polinomial M con la siguiente propiedad: para cualquier n , hay una cadena de aviso A de longitud f ( n ) tal que, para cualquier entrada x de longitud n , la máquina Mdecide correctamente el problema de la entrada x , dado x y A .
La clase de complejidad más común que involucra consejos es P / poli, donde la longitud del consejo f ( n ) puede ser cualquier polinomio en n . P / poly es igual a la clase de problemas de decisión tal que, para cada n , existe un circuito booleano de tamaño polinómico que decide correctamente el problema en todas las entradas de longitud n . Una dirección de la equivalencia es fácil de ver. Si, para cada n , hay un circuito booleano de tamaño polinómico A ( n ) que decide el problema, podemos usar una máquina de Turing que interprete la cadena de consejos como una descripción del circuito. Entonces, dada la descripción deA ( n ) como consejo, la máquina decidirá correctamente el problema en todas las entradas de longitud n . La otra dirección usa una simulación de una máquina de Turing de tiempo polinomial mediante un circuito de tamaño polinomial como en una prueba del teorema de Cook . Simular una máquina de Turing con asesoramiento no es más complicado que simular una máquina ordinaria, ya que la cadena de consejos se puede incorporar al circuito. [1]
Debido a esta equivalencia, P / poli se define a veces como la clase de problemas de decisión que se pueden resolver mediante circuitos booleanos de tamaño polinomial o circuitos booleanos no uniformes de tamaño polinómico .
P / poly contiene tanto P como BPP (teorema de Adleman). También contiene algunos problemas indecidibles , como la versión unaria de cada problema indecidible, incluido el problema de la detención . Por eso, no está contenido en DTIME ( f ( n )) o NTIME ( f ( n )) para ningún f .
Clases de asesoramiento se pueden definir para otros límites de recursos en lugar de P . Por ejemplo, tomando una máquina de Turing de tiempo polinomial no determinista con un consejo de longitud f ( n ) se obtiene la clase de complejidad NP / f ( n ) . Si se nos permite un consejo de longitud 2 n , podemos usarlo para codificar si cada entrada de longitud n está contenida en el idioma. Por lo tanto, cualquier función booleana es calculable con un consejo de longitud 2 n y un consejo de longitud superior a la exponencial no es significativo.
De manera similar, la clase L / poli se puede definir como espacio de registro determinista con una cantidad polinomial de consejos.
Los resultados conocidos incluyen:
- Las clases NL / poly y UL / poly son las mismas, es decir, el cálculo del espacio logarítmico no determinista con consejos puede hacerse inequívoco. [2] Esto puede demostrarse mediante un lema de aislamiento . [3]
- Se sabe que coNEXP está contenido en NEXP / poly . [4]
- Si NP está contenido en P / poli , entonces la jerarquía de tiempo polinomial colapsa ( teorema de Karp-Lipton ).
Referencias
- ^ Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, pág. 113, ISBN 9780521424264, Zbl 1193.68112.
- ^ Reinhardt, Klaus; Allender, Eric (2000). "Haciendo inequívoco el no determinismo". SIAM J. Comput . 29 (4): 1118-1131. CiteSeerX 10.1.1.55.3203 . doi : 10.1137 / S0097539798339041 . Zbl 0947.68063 .
- ↑ Hemaspaandra, Lane A .; Ogihara, Mitsunori (2002). El compañero de la teoría de la complejidad . Textos en Informática Teórica. Una serie EATCS. Berlín: Springer-Verlag . ISBN 3-540-67419-5. Zbl 0993.68042 .
- ^ Lance Fortnow , Un pequeño teorema
- Teoría de la complejidad computacional
