En teoría de la complejidad y teoría de la computabilidad , una máquina oráculo es una máquina abstracta que se utiliza 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 ciertos 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 ser concebida 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 puede ser, por ejemplo, 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 informático. El oráculo es simplemente una " caja negra " que es capaz de producir una solución para cualquier instancia de un problema computacional dado:
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í es de van Melkebeek (2003, p. 43).
Una máquina oráculo, como una máquina de Turing, incluye:
Además de estos componentes, una máquina oráculo también incluye:
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 solo paso computacional:
El efecto de cambiar al estado ASK es entonces recibir, en un solo paso, una solución a la instancia del problema que está escrita en la cinta del oráculo.
Existen muchas definiciones alternativas a la presentada anteriormente. Muchas de ellas están especializadas 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 oráculo a partir de un oráculo dado bajo todas estas definiciones si es computable por oráculo bajo 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, que utiliza una cinta de oráculo que puede tener su propio alfabeto.
La clase de complejidad de los problemas de decisión que se pueden resolver mediante un algoritmo de la clase A con un oráculo para un lenguaje L se denomina A L . Por ejemplo, P SAT es la clase de problemas que se pueden resolver en tiempo polinomial mediante una máquina de Turing determinista con un oráculo para el problema de satisfacibilidad booleano . 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 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 polinomial, P SAT = P NP . Sin embargo, si A = DLOGTIME , entonces A SAT puede no ser igual a A NP . (La definición de 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 suponer que la clase que define la máquina abstracta solo tiene acceso a un único oráculo para un lenguaje. En este contexto, no está definida si la clase de complejidad no tiene ningún problema completo con respecto a las reducciones disponibles para ).
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 conduce 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 , 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 relativiza en ambos sentidos se toma como evidencia de que responder a esta pregunta es difícil, porque una técnica de prueba que relativiza (es decir, no se ve 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 de entre todos los oráculos posibles (un conjunto infinito). En este caso se ha demostrado que, con una probabilidad de 1, P A ≠NP A . [7] 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 admiten una afirmación con una probabilidad de 0 o 1 solamente. (Esto se desprende de la ley cero-uno de Kolmogorov .) Esto 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; [ ¿ investigación 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]
En criptografía , los oráculos se utilizan para argumentar la seguridad de los protocolos criptográficos en los que se utiliza una función hash . Se da 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, como lo está la función hash. Una prueba de este tipo muestra que, a menos que el atacante resuelva el problema difícil en el corazón de la reducción de seguridad, debe hacer uso de alguna propiedad interesante de la función hash para romper el protocolo; no puede tratar la función hash como una caja negra (es decir, como un oráculo aleatorio).
