Máquina de Oracle

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Ayúdenos a mejorar este artículo introduciendo citas más precisas. ( Octubre de 2023 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Sistemas de caja negra
Sistema
Caja negra , máquina Oracle
Métodos y técnicas
Prueba de caja negra , Blackboxing
Técnicas relacionadas
Retroalimentación , Ofuscación , Reconocimiento de patrones , Caja blanca , Pruebas de caja blanca , Pruebas de caja gris , Identificación del sistema
Fundamentos
Información a priori , Sistemas de control , Sistemas abiertos , Investigación de operaciones , Sistemas termodinámicos
en a mi

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:

• Un problema de decisión se representa como un conjunto A de números naturales (o cadenas). Una instancia del problema es un número natural (o cadena) arbitrario. La solución de la instancia es "SÍ" si el número (cadena) está en el conjunto y "NO" en caso contrario.
• Un problema de función se representa mediante una función f de números naturales (o cadenas) a números naturales (o cadenas). Una instancia del problema es una entrada x para f . La solución es el valor f ( x ).

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:

• 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 única celda de la cinta de trabajo y puede leer los datos allí, escribir nuevos datos e incrementar o disminuir 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 mecanismo de control y cambiar estados) 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 de oráculo , que es una cinta semi-infinita separada de la cinta de trabajo. El alfabeto de la cinta de oráculo puede ser diferente del alfabeto de la cinta de trabajo.
• un cabezal de 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 del oráculo leyendo y escribiendo símbolos;
• dos estados especiales: el estado PREGUNTAR y el estado RESPUESTA.

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 contenido de la cinta del oráculo se considera una instancia del problema computacional del oráculo;
• Se consulta el oráculo y el contenido de la cinta del oráculo se reemplaza con la solución a esa instancia 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 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:

• Algunas definiciones, en lugar de escribir la respuesta en la cinta del oráculo, tienen dos estados especiales, SÍ y NO, además del estado ASK. Cuando se consulta el oráculo, se elige el siguiente estado como SÍ si el contenido de la cinta del oráculo está en el conjunto del oráculo, y como NO si el contenido no está en el conjunto del oráculo. ^[1]
• Algunas definiciones evitan la cinta de oráculo independiente. Cuando se ingresa el estado del oráculo, se especifica un símbolo de cinta. Se consulta al oráculo con la cantidad de veces que este símbolo de cinta aparece en la cinta de trabajo. Si ese número está en el conjunto del oráculo, el siguiente estado es el estado SÍ; si no lo está, el siguiente estado es el estado NO. ^[2]
• Otra definición alternativa hace que la cinta oracular sea de solo lectura y elimina por completo los estados ASK y RESPONSE. Antes de que se inicie la máquina, la función indicadora del conjunto oracular se escribe en la cinta oracular utilizando los símbolos 0 y 1. La máquina puede entonces consultar el oráculo escaneando hasta el cuadrado correcto en la cinta oracular y leyendo el valor ubicado allí. ^[3]

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:

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

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 ).$Estilo de visualización A^{B}}$${\estilo de visualización A}$$Estilo de visualización A^{B}}$${\estilo de visualización B}$${\estilo de visualización 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 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).