¿Por qué la relativización no puede resolver NP !=P?

Question

Si este problema es realmente estúpido, por favor, ciérralo. Pero realmente quiero obtener alguna respuesta para él. Y aprendí complejidad computacional sólo leyendo libros.

Cuando aprendí el tema de la relativización y las máquinas de oráculo, leí el siguiente teorema:

Existen oráculos A, B tales que $P^A = NP^A$ y $P^B \neq NP^B$ .

Y luego el libro decía que debido a esto, no podemos resolver el problema de NP = P utilizando la relativización. Pero creo que lo que implica es que $NP \neq P$ . El razonamiento es el siguiente:

En primer lugar, es bastante fácil verlo:

$$A = B \Leftrightarrow \forall \text{oracle O, }A^O = B^O$$

Aunque creo que es obvio, sigo dándole una prueba:

Una prueba sencilla de NP != P ?

Y su negación lo es:

$$A \neq B \Leftrightarrow \exists \text{oracle O such that } A^O \neq B^O$$

Por lo tanto, dado que existe un oráculo B tal que:

$$NP^B \neq P^B$$

podemos concluir que $NP \neq P$

¿Cuál es el problema con el razonamiento anterior?

Answer 1

La declaración $A = B \rightarrow \forall O \; A^O = B^O$ es incorrecta. Por ejemplo, se sabe que $\mathrm{IP} = \mathrm{PSPACE}$ pero sabemos que existe un oráculo $A$ tal que $\mathrm{IP}^A \ne \mathrm{PSPACE}^A$ .

La sustitución directa no funciona aquí, porque diferentes caracterizaciones de una clase concreta pueden comportarse de forma diferente cuando las relativizamos.

Answer 2

Los demás han señalado el fallo de tu argumento sugerido, pero permíteme discutir algo de la primera parte de tu post.

La conclusión del resultado de relativización de Baker-Gill-Solovay (que existen oráculos $A$ y $B$ para lo cual $P^A=NP^A$ y $P^B\neq NP^B$ ) no es que "no podemos resolver el problema de NP=P por relativización", como tú dices, sino algo más profundo: la conclusión es que no podemos resolver el problema de NP=P por cualquier método que admita la relativización . Se trata de una clase enorme de métodos, que incluye todos los métodos potentes estándar de la teoría de la computabilidad. La razón es que si pudiéramos demostrar $P=NP$ o $P\neq NP$ utilizando métodos que puedan acomodar oráculos, entonces deduciríamos inmediatamente la igualdad o desigualdad correspondiente para todos los oráculos, en contradicción con el resultado de Baker-Gill-Solovay.

El significado de esto es que, puesto que todos los métodos estándar admiten la relativización, no podremos resolver P frente a NP utilizando sólo esos métodos; debemos ser más imaginativos y sutiles.

Es decir, la cuestión no es que el teorema descarte el método de relativización como método para resolver P contra NP, sino que descarta todos los métodos que tienen en cuenta la relativización. Dado que esto incluye la mayoría de nuestros métodos, es un obstáculo serio.

Answer 3

El mapa $A \to A^O$ no depende sólo de los elementos contenidos en el lenguaje $O$ por lo que no es una operación sobre las lenguas. Depende de la forma semántica en que el lenguaje $A$ se define. Por ejemplo, $NP^O$ está permitido ambos nondeterminismo y acceso a $O$ . $P^O$ se permite un tiempo polinómico determinista y el acceso a $O$ . Creo que es cierto que $BPP$ puede separarse de $P$ aunque se cree que $BPP = P$ .

Answer 4

Estaba aplazando la publicación de una no-respuesta, pero estoy animado por JDH.

Todavía hay algo profundamente desconcertante en la idea de que si $A = B$ posiblemente haya un oráculo para el que $A^O \ne B^O$ y ese parece ser el quid de la cuestión de la OP. En ese sentido, el ejemplo de ilyaraj de IP y PSPACE es en realidad mejor, porque a diferencia de P y NP, donde no conocemos la verdadera respuesta, en realidad SABEMOS que IP = PSPACE, y sin embargo todavía hay un oráculo que los separa.

Pero creo que una explicación más profunda tiene que ir más allá de la relativización, a las propiedades en las que se basa la relativización. El libro de Arora-Barak lo explica bastante bien En cuanto a las pruebas, señalan que pruebas como la diagonalización se basan en una simulación eficiente (universalidad) y en la capacidad de enumerar máquinas (enumeración), y que cualquier resultado basado en un oráculo se basa ÚNICAMENTE en estas dos propiedades.

Por lo tanto, la respuesta real a por qué P vs NP es independiente de los argumentos relativizados es que se necesita explotar más información que la mera universalidad y enumeración. Esto viene a colación precisamente por la "nueva" barrera que suponen los debates sobre las pruebas de Deolalikar, según la cual las técnicas de prueba que intentan diferenciar la geometría de las soluciones de los problemas SAT frente a los problemas P no pueden funcionar.

Answer 5

Y, por supuesto, esto es exactamente lo que ocurre en el $\mathrm{IP}^A \ne \mathrm{PSPACE}^A$ prueba -- IP se define por su acceso a información externa, que puede considerarse similar a un oráculo -- mientras que PSPACE no. En el sentido más superficial, tanto el IP-verificador como el IP-prover tienen acceso a un oráculo de bits aleatorios. Las máquinas PSPACE en general no lo tienen. Una forma superficial de ver esto, sin siquiera hacer referencia a la prueba (que francamente he olvidado) es que conceder a IP un oráculo de bits aleatorios por definición le haría daño. Pero conceder a PSPACE un oráculo de bits aleatorios podría mejorar su capacidad de cálculo.