Máquina de oráculo

Compartir Imprimir Citar

Máquina abstracta utilizada para estudiar problemas de decisión

En la teoría de la complejidad y la teoría de la computabilidad, una máquina oracular 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 detención.

Oráculos

Una máquina de 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 que 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 dado:

Un problema de decisión está representado como un conjunto A de números naturales (o cadenas). Un caso del problema es un número natural arbitrario (o cadena). La solución a la instancia es "SÍ" si el número (cadena) está en el conjunto, y "NO" de otra manera.
Un problema de función está representado por 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 de oráculo puede realizar todas las operaciones habituales de una máquina de Turing y también puede consultar el 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 del oráculo proporciona al oráculo un número natural y el oráculo responde con un "sí" o "no" indicando si ese número es un elemento de A.

Definiciones

Hay muchas definiciones equivalentes de las máquinas de Turing de Oracle, como se explica a continuación. El que se presenta aquí es de van Melkebeek (2000:43).

Una máquina de Oracle, como una máquina de Turing, incluye:

a cinta de trabajo: una secuencia de células sin principio o fin, cada una de las cuales puede contener una B (para blanco) o un símbolo del alfabeto de cinta;
a read/write head, que descansa en una sola célula de la cinta de trabajo y puede leer los datos allí, escribir nuevos datos, y aumentar o decrementar su posición a lo largo de la cinta;
a 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 los datos que se lean.

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

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

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

el contenido de la cinta del oráculo se ve como una instancia del problema computacional del oráculo;
el oráculo es consultado, y el contenido de la cinta del oráculo se reemplaza por la solución a esa instancia del problema;
la cabeza del oráculo se mueve a la primera plaza en la cinta del oráculo;
el estado de la máquina del oráculo se cambia a RESPONSE.

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.

Definiciones alternativas

Existen muchas definiciones alternativas a la presentada anteriormente. Muchos de estos están especializados para el caso en que el oráculo resuelve un problema de decisión. En este caso:

Algunas definiciones, en lugar de escribir la respuesta a la cinta del oráculo, tienen dos estados especiales SÍ y NO además del estado ASK. Cuando se consulta el oráculo, el siguiente estado es elegido para ser SI si el contenido de la cinta del oráculo está en el conjunto del oráculo, y elegido al NO si el contenido no está en el conjunto del oráculo (Adachi 1990:111).
Algunas definiciones bloquean la cinta de oráculo separada. Cuando se introduce el estado del oráculo, se especifica un símbolo de cinta. El oráculo se pregunta con el número 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 de SI; si no lo es, el siguiente estado es el estado NO (Rogers 1967:129).
Otra definición alternativa hace que la cinta de oráculo sólo sea leída, y elimina completamente los estados ASK y RESPONSE. Antes de que se inicie la máquina, la función indicadora del conjunto del oráculo está escrita en la cinta del oráculo utilizando símbolos 0 y 1. La máquina es capaz de preguntar el oráculo escaneando a la plaza correcta en la cinta del oráculo y leyendo el valor localizado allí (Soare 1987:47, Rogers 1967:130).

Estas definiciones son equivalentes desde el punto de vista de la computabilidad de Turing: una función es computable por Oracle desde un oráculo dado bajo todas estas definiciones si es computable por Oracle 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, utilizando una cinta de oráculo que puede tener su propio alfabeto.

Clases de complejidad de Oracle Machines

La clase de complejidad de los problemas de decisión que puede resolver 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 polinómico mediante una máquina de Turing determinista con un oráculo para el problema booleano de satisfacibilidad. La notación A^B se puede extender a un conjunto de lenguajes B (o una clase de complejidad B), usando la siguiente definición:

A^{B}=bigcup _{Lin B}A^{L}

Cuando un idioma L está completo para alguna clase B, entonces A^L= A^B siempre que las máquinas en A pueden ejecutar reducciones utilizadas en la definición de la integridad de la clase B. En particular, dado que el SAT está completo con respecto a las reducciones de tiempo polinomio, P^SAT= P^NP. Sin embargo, si A = DLOGTIME, entonces A^SAT no igual A^NP. (Nota que la definición de ${displaystyle A^{B}}$ dado arriba no es completamente estándar. En algunos contextos, como la prueba del tiempo y la jerarquía espacial teoremas, es más útil asumir que la máquina abstracta que define clase $A$ sólo tiene acceso a un oráculo único para un idioma. En este contexto, ${displaystyle A^{B}}$ no se define si la clase de complejidad $B$ no tiene ningún problema completo con respecto a las reducciones disponibles $A$ .)

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

Las máquinas de 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 (Baker, Gill y Solovay 1975). 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 relativiza (es decir, que no se ve afectada por la adición de un oráculo) no responderá a la pregunta P = pregunta NP. La mayoría de las técnicas de demostración relativizan.

Se puede considerar el caso en que un oráculo se elige 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 (Bennett y Gill 1981). 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 respaldan una declaración con probabilidad 0 o 1 solamente. (Esto se deduce de la ley cero-uno de Kolmogorov). Esta es solo una evidencia débil de que P≠NP, ya que una declaració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 (Chang et al., 1994).

Oráculos y problemas de detención

Una máquina con un oráculo para el problema de la detención puede determinar si las máquinas de Turing particulares 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 (Börger 1989).

Aplicaciones a la criptografía

En criptografía, los oráculos se utilizan para presentar argumentos a favor de la seguridad de los protocolos criptográficos en los que se utiliza una función hash. Se otorga una reducción de seguridad para el protocolo en el caso de que, en lugar de una función hash, un oráculo aleatorio responda cada consulta de manera 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. Tal prueba muestra que, a menos que el atacante resuelva el problema central de la reducción de la 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).