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 misma. 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 consejos A de longitud f ( n ) tal que, para cualquier entrada x de longitud n , la máquina M decide correctamente el problema sobre la entrada x , dado x y A .

La clase de complejidad más común que involucra consejos es P/poly , 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 tales que, para cada n , existe un circuito booleano de tamaño polinomial que decide correctamente el problema para todas las entradas de longitud n . Una dirección de la equivalencia es fácil de ver. Si, para cada n , existe un circuito booleano de tamaño polinomial A ( n ) que decide el problema, podemos usar una máquina de Turing que interpreta la cadena de consejos como una descripción del circuito. Entonces, dada la descripción de A ( n ) como consejo, la máquina decidirá correctamente el problema para todas las entradas de longitud n . La otra dirección utiliza una simulación de una máquina de Turing de tiempo polinomial mediante un circuito de tamaño polinomial, como en una demostración 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 se define a veces como la clase de problemas de decisión que se pueden resolver mediante circuitos booleanos de tamaño polinomial, o mediante circuitos booleanos no uniformes de tamaño polinomial .

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 parada . Debido a eso, no está contenido en DTIME ( f ( n )) ni en NTIME ( f ( n )) para ninguna f .

Se pueden definir clases de consejos para otros límites de recursos en lugar de P. Por ejemplo, una máquina de Turing polinomial no determinista con un consejo de longitud f ( n ) da como resultado la clase de complejidad NP / f ( n ) . Si se 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 ²ⁿ , y un consejo de longitud mayor que la exponencial no tiene sentido.

De manera similar, la clase L/poly puede definirse como un espacio logarítmico determinista con una cantidad polinómica de consejos.

Los resultados conocidos incluyen:

• Las clases NL/poly y UL/poly son iguales, es decir, el cálculo no determinista del espacio logarítmico con consejos puede hacerse inequívoco. ^{[ 2 ]} Esto puede probarse 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 polinomial colapsa ( teorema de Karp-Lipton ).