Máquina oráculo

En la teoría de la complejidad y la teoría de la computabilidad , una máquina oráculo es una máquina abstracta que puede consultar una caja negra llamada oráculo , la cual es capaz de dar una respuesta a cualquier instancia de un problema determinado .${\displaystyle R}$en una sola operación. El problema${\displaystyle R}$⁠ puede ser de cualquier clase de complejidad , o incluso puede ser un problema indecidible como el problema de la parada . Si otro problema ⁠${\displaystyle R'}$es reducible a​​${\displaystyle R}$⁠ en tiempo polinomial , entonces la máquina oráculo (con el ⁠${\displaystyle R}$-oracle ) puede resolver${\displaystyle R'}$en tiempo polinomial; se puede decir que${\displaystyle R'}$pertenece a la clase de complejidad relativizada .${\displaystyle {\mathsf {P}}^{R}}$⁠ . Otras clases de complejidad relativizadas como ⁠${\displaystyle {\mathsf {NP}}^{R}}$⁠ puede definirse de forma análoga. ^{[ 1 ]}

Una máquina oráculo puede concebirse como una máquina de Turing conectada a un oráculo . El oráculo, en este contexto, es una entidad capaz de resolver algún problema, que por ejemplo puede ser un problema de decisión o un problema funcional . El problema no tiene por qué ser computable; no se presupone que el oráculo sea una máquina de Turing o un programa informático. El oráculo es simplemente una " caja negra " capaz de producir una solución para cualquier instancia de un problema computacional dado .

• Un problema de decisión se representa como un conjunto A de números naturales (o cadenas de caracteres ). Una instancia del problema es un número natural (o cadena de caracteres) arbitrario. La solución a la instancia es "SÍ" si el número (o cadena de caracteres) pertenece al conjunto, y "NO" en caso contrario.
• Un problema de función se representa mediante una relación binaria R que relaciona números naturales (o cadenas) con números naturales (o cadenas). Una instancia del problema es una entrada x para R. Una solución es un valor relacionado con x mediante R.

Una máquina oráculo puede realizar todas las operaciones habituales de una máquina de Turing, y también puede consultar al oráculo para obtener una solución a cualquier instancia del problema computacional para ese oráculo. Por ejemplo, si el problema es un problema de decisión para un conjunto A de números naturales, la máquina oráculo le proporciona al oráculo un número natural, y el oráculo responde con "sí" o "no" indicando si ese número es un elemento de A.

Existen muchas definiciones equivalentes de máquinas de Turing oráculo, como se analiza a continuación. La que se presenta aquí proviene de van Melkebeek (2003 , p. 43) . 

Una máquina oráculo, como una máquina de Turing, incluye:

• una cinta de trabajo : una secuencia de celdas sin principio ni fin, cada una de las cuales puede contener una B (de espacio en blanco) o un símbolo del alfabeto de la cinta;
• un cabezal de lectura/escritura , que descansa sobre una sola celda de la cinta de trabajo y puede leer los datos allí, escribir nuevos datos e incrementar o decrementar su posición a lo largo de la cinta;
• un mecanismo de control , que puede estar en uno de un número finito de estados , y que realizará diferentes acciones (leer datos, escribir datos, mover el cabezal de lectura/escritura y cambiar de estado) dependiendo del estado actual y de los datos que se estén leyendo.

Además de estos componentes, una máquina oráculo también incluye:

• una cinta oráculo , que es una cinta semiinfinita separada de la cinta de trabajo. El alfabeto para la cinta oráculo puede ser diferente del alfabeto para la cinta de trabajo.
• un cabezal oráculo que, al igual que el cabezal de lectura/escritura, puede moverse hacia la izquierda o hacia la derecha a lo largo de la cinta oráculo leyendo y escribiendo símbolos;
• dos estados especiales: el estado ASK y el estado RESPONSE.

De vez en cuando, la máquina oráculo puede entrar en el estado ASK. Cuando esto sucede, se realizan las siguientes acciones en un único paso computacional:

• El contenido de la cinta del oráculo se considera una instancia del problema computacional del oráculo;
• Se consulta al oráculo y el contenido de la cinta del oráculo se reemplaza con la solución a ese caso particular del problema;
• La cabeza del oráculo se mueve al primer cuadrado de la cinta del oráculo;
• El estado de la máquina oráculo cambia a RESPUESTA.

El efecto de cambiar al estado ASK es, por lo tanto, recibir, en un solo paso, una solución a la instancia del problema que está escrita en la cinta del oráculo.

La clase de complejidad de problemas de decisión resolubles por un algoritmo de clase A con un oráculo para un lenguaje L se denomina A ^L . Por ejemplo, P ^SAT es la clase de problemas resolubles en tiempo polinomial por una máquina de Turing determinista con un oráculo para el problema de satisfacibilidad booleana . La notación A ^B puede extenderse a un conjunto de lenguajes B (o una clase de complejidad B ), utilizando la siguiente definición:

${\displaystyle A^{B}=\bigcup _{L\in B}A^{L}}$

Cuando un lenguaje L es completo para alguna clase B , entonces A ^L = A ^B siempre que las máquinas en A puedan ejecutar reducciones utilizadas en la definición de completitud de la clase B. En particular, dado que SAT es NP-completo con respecto a reducciones de tiempo polinomial, P ^SAT =P ^NP . Sin embargo, si A = DLOGTIME , entonces A ^SAT puede no ser igual a A ^NP . (La definición de${\displaystyle A^{B}}$Lo dado anteriormente no es completamente estándar. En algunos contextos, como la demostración de los teoremas de jerarquía de tiempo y espacio , es más útil asumir que la máquina abstracta define la clase${\displaystyle A}$solo tiene acceso a un único oráculo para un solo idioma. En este contexto,${\displaystyle A^{B}}$no está definido si la clase de complejidad${\displaystyle B}$no tiene ningún problema completo con respecto a las reducciones disponibles para${\displaystyle A}$.)

Se entiende que NP ⊆ P ^NP , pero la cuestión de si NP ^NP , P ^NP , NP y P son iguales sigue siendo, en el mejor de los casos, tentativa. Se cree que son diferentes, y esto lleva a la definición de la jerarquía polinómica .

Las máquinas oráculo son útiles para investigar la relación entre las clases de complejidad P y NP , al considerar la relación entre P ^A y NP ^A para un oráculo A. En particular, se ha demostrado que existen lenguajes A y B tales que P ^A =NP ^A y P ^B ≠ NP ^{B. [ 5} ] El hecho ^de que la pregunta P = NP relativice en ambos sentidos se toma como evidencia de que responder a esta pregunta es difícil, porque cualquier técnica de prueba que relativice (es decir, que no se vea afectada por la adición de un oráculo) no responderá a la pregunta P = NP. ^{[ 6 ]} La mayoría de las técnicas de prueba relativizan. ^{[ 7 ]}

^{Se puede considerar el caso en que se elige un oráculo al} azar entre todos los oráculos posibles (un conjunto infinito ). Se ha demostrado en este caso que, con probabilidad 1, P ^A ≠ NP ^{A. [ 8} ] Cuando una pregunta es verdadera para casi todos los oráculos, se dice que es verdadera para un oráculo aleatorio . Esta elección de terminología se justifica por el hecho de que los oráculos aleatorios solo admiten una afirmación con probabilidad 0 o 1. (Esto se deduce de la ley cero-uno de Kolmogorov ). Esto es solo una evidencia débil de que P ≠ NP, ya que una afirmación puede ser verdadera para un oráculo aleatorio pero falsa para las máquinas de Turing ordinarias; por ejemplo, IP ^A ≠ PSPACE ^A para un oráculo aleatorio A pero IP = PSPACE . ^{[ 9 ]}

Una máquina con un oráculo para el problema de la parada puede determinar si determinadas máquinas de Turing se detendrán con entradas específicas, pero no puede determinar, en general, si las máquinas con oráculo como ella (es decir, equipadas con un oráculo para el problema de la parada) se detendrán. Esto crea una jerarquía de máquinas, cada una con un oráculo de parada más potente y un problema de parada aún más difícil. Esta jerarquía de máquinas puede utilizarse para definir la jerarquía aritmética . ^{[ 10 ]}

En criptografía , los oráculos se utilizan para argumentar a favor de la seguridad de los protocolos criptográficos que emplean una función hash . Se proporciona una reducción de seguridad (prueba de seguridad) para el protocolo cuando, en lugar de una función hash, un oráculo aleatorio responde a cada consulta de forma aleatoria pero consistente; se supone que el oráculo está disponible para todas las partes, incluido el atacante, al igual que la función hash. Dicha prueba demuestra que, a menos que el atacante resuelva el problema fundamental de la reducción de seguridad, deberá aprovechar alguna propiedad interesante de la función hash para vulnerar el protocolo; no puede tratar la función hash como una caja negra (es decir, como un oráculo aleatorio).