Consejo (complejidad computacional)
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 un tiempo polinómico en la máquina de Turing 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 M decide correctamente el problema en la entrada x, dados x y A.
La clase de complejidad más común que implica asesoramiento es P/poly, donde la longitud de asesoramiento/consejo f(n) puede ser cualquier polinomio en n. P/poly es igual a la clase de problemas de decisión de modo 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 de las direcciones de la equivalencia es fácil de ver: si, por cada n, hay un circuito booleano A(n) de tamaño polinómico que decide el problema, podemos usar una máquina de Turing que interpreta la cadena de consejos como una descripción del circuito. Luego, dada la descripción de A(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 polinómico mediante un circuito de tamaño polinómico como en una prueba del Teorema de Cook. Simular una máquina de Turing con consejos 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/poly a veces se define como la clase de problemas de decisión que se pueden resolver mediante circuitos booleanos de tamaño polinómico o mediante circuitos booleanos no uniformes de tamaño polinómico.
P/poly contiene P y BPP (teorema de Adleman). También contiene algunos problemas indecidibles, como la versión unaria de cada problema indecidible, incluido el problema de la parada. Debido a eso, no está contenido en DTIME(f(n)) o NTIME(f(n)) para ninguna f.
Las clases de consejos se pueden definir para otros límites de recursos en lugar de P. Por ejemplo, tomar una máquina de Turing de tiempo polinomial no determinista con un consejo de longitud f(n) da la clase de complejidad NP/f(n). Si se nos permite un consejo de longitud 2n, podemos usarlo para codificar si cada entrada de longitud n está contenida en el lenguaje. Por lo tanto, cualquier función booleana es computable con un consejo de longitud 2n y un consejo de longitud más que exponencial no es significativo.
De manera similar, la clase L/poly se puede definir como espacio de registro determinista con una cantidad polinómica 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 asesoramiento puede hacerse inequívoco.[2] Esto se puede probar usando un lema de aislamiento.[3]
- Se sabe que coNEXP está contenido en NEXP/poly.[4]
- Si NP está contenido en P/poly, entonces la jerarquía de tiempo polinómica se colapsa (teorema de Karp-Lipton).
Referencias editar
- ↑ Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, p. 113, ISBN 9780521424264.
- ↑ Reinhardt, Klaus; Allender, Eric (2000). «Making nondeterminism unambiguous». SIAM J. Comput. 29 (4): 1118-1131. doi:10.1137/S0097539798339041.
- ↑ Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002). The complexity theory companion. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-67419-5.
- ↑ Lance Fortnow, A Little Theorem Archivado el 5 de agosto de 2019 en Wayback Machine.
Datos: Q4686786
