A pesar de que el extraño nombre que suena, oráculos son de hecho parte de matemáticas serias.
Un oráculo de la máquina es una máquina de Turing equipado con algunos infinita cadena binaria, los bits de los cuales se pueden consultar durante su funcionamiento. Hay dos cosas que he escuchado la frase de "oracle resultado" o "oracle prueba" se utiliza para describir:
El primero es el uso de oracle máquinas para probar los resultados en la teoría de la computabilidad. Esto no significa que el oráculo de la máquina proporciona la prueba; por el contrario, que la prueba es obtenido mediante, entre otras cosas, probar algunos hechos acerca de oracle máquinas y, a continuación, el uso de ellos, es decir, que de oracle máquinas son relevantes los objetos matemáticos para que el problema sea resuelto. Por ejemplo, la existencia de un mínimo de Turing grados por debajo de lo $0''$ tiene una prueba que consiste en probar cosas acerca de oracle máquinas, así como una prueba de que no. Esto no es lo que Gasarch medios, pero vale la pena ser consciente de.
La segunda - y relevantes - significado es, los resultados que se relativiza a un oráculo. Para cualquier fijos de oracle $A$, podemos definir la complejidad de las clases de $P^A$ y $NP^A$: $P^A$ es la clase de problemas resueltos por una máquina con $A$ como un oráculo en el polinomio de tiempo, y de manera similar para $NP^A$. Otro ejemplo de relativizada definiciones en la teoría de la complejidad es el polinomio de jerarquía de tiempo, donde cada nivel sucesivo se compone de los problemas que tienen solución en el polinomio de tiempo por las máquinas, dado un conjunto desde el nivel anterior como un oráculo.
Ahora, a menudo en la teoría de la computabilidad, teoremas relativizar: si algo es verdadero acerca de dos computabilidad teoría de las clases, es cierto que de esas mismas clases en relación a cualquier oracle. Por ejemplo, es un resultado estándar (Friedberg-Muchnik teorema) que no son incomparables.c.e. grados; y la prueba de muestra de inmediato en el hecho de que para cualquier conjunto a $A$, hay incomparable grados que son c.e. en relación a $A$.
Por el contrario - y esto es lo que Gasarch se refiere a este tipo de relativización no tienden a mantener en la teoría de la complejidad! En particular, Baker, Gill, y Solovay demostrado que:
Así, sin embargo, $P$ vs $NP$ se ha resuelto, la prueba dependerá específicamente en las propiedades de la real $P$ $NP$ ; tratando de relativizar es arbitraria oráculos necesariamente va a romper algo.
Ahora, Gasarch dice que este resultado es útil en la comprensión de lo que las técnicas no pueden ser utilizadas para solucionar $P$ vs $NP$. La razón de esto es que podemos mostrar que un número de técnicas que se están relativizando: por ejemplo, si se podía usar para separar $P$ $NP$ (o probar equivalente), también se puede utilizar para separar $P^A$ $NP^A$ (o probar equivalente) para cualquier oracle $A$. Por EGB, esto significa que aquellos a prueba las técnicas no pueden ser utilizados para resolver $P$ vs $NP$.
Existen otras barreras para responder a $P$ vs $NP$, los cuales son de un sabor similar - en particular, las "pruebas naturales" barrera de Razborov y Rudich. Pero la relativización de la barrera fue la primera gran barrera descubierto, y por mucho, el más sencillo de estado y de probar.
