En la teoría de la complejidad y la teoría de la computabilidad , una máquina oráculo es una máquina abstracta utilizada para estudiar problemas de decisión . Se puede visualizar como una máquina de Turing con una caja negra , llamada oráculo , que es capaz de resolver determinados problemas en una sola operación. El problema puede ser de cualquier clase de complejidad . Incluso se pueden utilizar problemas indecidibles , como el problema de la detención .
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 de función . El problema no tiene por qué ser computable; No se supone que el oráculo sea una máquina de Turing o un programa de computadora. El oráculo es simplemente una " caja negra " que es capaz de producir una solución para cualquier instancia de un problema computacional determinado:
Una máquina Oracle puede realizar todas las operaciones habituales de una máquina de Turing y también puede consultar al Oracle para obtener una solución a cualquier instancia del problema computacional de ese Oracle. Por ejemplo, si el problema es un problema de decisión para un conjunto A de números naturales, la máquina del 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 las máquinas de Turing de Oracle, como se analiza a continuación. El que se presenta aquí es de van Melkebeek (2003, p. 43).
Una máquina Oracle, como una máquina de Turing, incluye:
Además de estos componentes, una máquina Oracle también incluye:
De vez en cuando, la máquina Oracle puede entrar en el estado PREGUNTAR. Cuando esto sucede, las siguientes acciones se realizan en un solo paso computacional:
El efecto de cambiar al estado ASK es recibir, en un solo paso, una solución a la instancia del problema que está escrita en la cinta de Oracle.
Existen muchas definiciones alternativas a la presentada anteriormente. Muchos de ellos están especializados para el caso en el que el oráculo resuelve un problema de decisión. En este caso:
Estas definiciones son equivalentes desde el punto de vista de la computabilidad de Turing: una función es computable por Oracle a partir de un oráculo dado según todas estas definiciones si es computable por Oracle según cualquiera de ellas. Sin embargo, las definiciones no son equivalentes desde el punto de vista de la complejidad computacional. En general, se requiere una definición como la de van Melkebeek, utilizando una cinta de oráculo que puede tener su propio alfabeto.
La clase de complejidad de los problemas de decisión que pueden resolverse mediante un algoritmo de clase A con un oráculo para un lenguaje L se llama A L. Por ejemplo, P SAT es la clase de problemas que se pueden resolver en tiempo polinomial mediante una máquina determinista de Turing con un oráculo para el problema de satisfacibilidad booleana . La notación A B se puede extender a un conjunto de lenguajes B (o una clase de complejidad B), utilizando la siguiente definición:
Cuando un lenguaje L está completo para alguna clase B, entonces A L =A B siempre que las máquinas en A puedan ejecutar las reducciones utilizadas en la definición de completitud de la clase B. En particular, dado que SAT es NP-completo con respecto a las reducciones de tiempo polinomiales, P SAT = P NP . Sin embargo, si A = DLOGTIME , entonces A SAT puede no ser igual a A NP . (La definición dada anteriormente no es completamente estándar. En algunos contextos, como la prueba de los teoremas de jerarquía de tiempo y espacio , es más útil asumir que la clase que define la máquina abstracta solo tiene acceso a un único oráculo para un idioma. En este contexto, no se define si la clase de complejidad no tiene ningún problema completo con respecto a las reducciones disponibles .)
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, provisional. Se cree que son diferentes, y esto lleva a la definición de jerarquía polinomial .
Las máquinas Oracle son útiles para investigar la relación entre las clases de complejidad P y NP , considerando 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 . [4] 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 una 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. [5] La mayoría de las técnicas de prueba relativizan. [6]
Se puede considerar el caso en el 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 . [7] Cuando una pregunta es cierta para casi todos los oráculos, se dice que es cierta para un oráculo aleatorio . Esta elección de terminología se justifica por el hecho de que los oráculos aleatorios respaldan una afirmación con probabilidad 0 o 1 únicamente. (Esto se desprende de la ley cero-uno de Kolmogorov .) Esta es sólo 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; [ ¿ investigacion original? ] por ejemplo, IP A ≠PSPACE A para un oráculo aleatorio A pero IP = PSPACE . [8]
Una máquina con un oráculo para el problema de la detención puede determinar si determinadas máquinas de Turing se detendrán ante determinadas entradas, pero no puede determinar, en general, si las máquinas equivalentes a ella se detendrán. Esto crea una jerarquía de máquinas, cada una con un oráculo de detención más poderoso y un problema de detención aún más difícil. Esta jerarquía de máquinas se puede utilizar para definir la jerarquía aritmética . [9] [ página necesaria ]
En criptografía , los oráculos se utilizan para argumentar a favor de la seguridad de los protocolos criptográficos donde se utiliza una función hash . Se otorga una reducción de seguridad para el protocolo en el caso en que, 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. Tal prueba muestra que, a menos que el atacante resuelva el difícil problema central de la reducción de seguridad, debe hacer uso de alguna propiedad interesante de la función hash para romper el protocolo; no pueden tratar la función hash como una caja negra (es decir, como un oráculo aleatorio).
