¿Por qué la relativización es una barrera?

Cuando estaba explicando la prueba de Baker-Gill-Solovay de que existe un oráculo con el que podemos tener, , y un oráculo con el que podemos tener a un amigo, surgió una pregunta de por qué tales técnicas no son adecuadas para probar el problema , y no pude dar una respuesta satisfactoria.P ≠ N P P ≠ N $\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Para decirlo más concretamente, si tengo un enfoque para probar y si pudiera construir oráculos para hacer que una situación como la anterior ocurra, ¿por qué invalida mi método?$\mathsf{P} \neq \mathsf{NP}$

¿Alguna exposición / pensamiento sobre este tema?

Para decirlo de manera más concreta, si tengo un enfoque para probar P ≠ NP y si pudiera construir oráculos para que suceda una situación como la anterior, ¿por qué invalida mi método?

Tenga en cuenta que el último "si" no es una condición, porque Baker, Gill y Solovay ya construyeron tal oráculo. Es solo una verdad matemática que (1) existe un oráculo en relación con el cual P = NP, y que (2) existe un oráculo en relación con el cual P ≠ NP.

Esto significa que si tiene un enfoque para probar P ≠ NP y la misma prueba resultaría igualmente un resultado más fuerte "P ^A ≠ NP ^A para todos los oráculos A ", entonces su enfoque está condenado al fracaso porque contradeciría (1).

En otras palabras, hay una diferencia fundamental entre probar P ≠ NP y probar, por ejemplo, el teorema de la jerarquía de tiempo, porque la prueba de este último solo usa diagonalización y es igualmente aplicable a cualquier mundo relativizado.

Por supuesto, esto no significa que no haya pruebas de P ≠ NP. Dicha prueba (si existe) debe dejar de probar el resultado más fuerte mencionado anteriormente. En otras palabras, alguna parte de la prueba debe distinguir el mundo no relativizador de los mundos arbitrarios relativizados.

Ya hay buenas respuestas, pero me gustaría agregar algunos puntos pequeños.

Suponga que tenemos una técnica para resolver problemas, por ejemplo, diagonalización . Supongamos que queremos mostrar que la técnica no puede resolver un problema específico, por ejemplo, vs. . ¿Cómo se puede mostrar esto?N $\mathsf{P}$$\mathsf{NP}$

Antes de continuar, tenga en cuenta que una técnica como la diagonalización no es un concepto formal aquí (aunque podemos hacerlo así). Además, el hecho de que la técnica no pueda resolver el problema por sí sola no significa que no sea útil para resolver el problema, podríamos modificarlo y / o combinarlo con otras técnicas para resolver el problema.

Ahora, volvamos a la pregunta. Una forma de mostrar que una técnica no puede resolver un problema específico es mostrar que si pudiera, también funcionaría en un marco diferente para resolver otra pregunta, y la respuesta que obtendríamos en ese caso sería incorrecta. Esto es lo que pasa aquí. Si la diagonalización podría separar de , entonces el mismo argumento podría ser utilizado para separar de para todos . Pero sabemos que hay un oráculo que es falso (tome el problema completo como el oráculo). Por lo tanto, la diagonalización no puede separar de .P N P A P A A P S p a c e N P $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP^A}$$\mathsf{P^A}$$A$$\mathsf{PSpace}$$\mathsf{NP}$$\mathsf{P}$

El punto esencial en este argumento es una especie de principio de transferencia :

podemos transferir un argumento de diagonalización para TMs sin oráculo a TMs con oráculos.

Esto es posible aquí porque los argumentos de diagonalización se basan en la simulación de máquinas, además, la simulación no depende de las partes internas de las máquinas, sino solo de las respuestas finales de estas simulaciones. Este tipo de diagonalización se denomina diagonalización simple . En una simulación, no importa cómo funcione la máquina, solo nos importa la respuesta final de la máquina. Agregar un oráculo no cambiará esto, por lo que la simulación y el argumento funcionarán también en el marco donde tenemos oráculos.

Más formalmente, podemos pensar en un argumento de diagonalización como una función de una clase de máquinas (digamos ) a instancias que muestran que la máquina no puede resolver un problema (digamos ). Esta función de contraejemplo es la función de diagonalización. Una diagonalización es simple si los contraejemplos que proporciona no dependen de los componentes internos de las máquinas, es decir, si dos DTM de tiempo polinomial tienen el mismo lenguaje, el contraejemplo que muestra que no pueden resolver dado por la función de diagonalización es el mismo. S A T S A $\mathsf{P}$$SAT$$SAT$

¿Te preguntarás si esto es una gran restricción? ¿Por qué el contraejemplo debería depender de la estructura interna de la máquina? ¿Podemos probar separaciones usando diagonalización que no pueden probarse usando diagonalización simple? La respuesta es sí. De hecho, Kozen muestra en su artículo de 1978 "Indexación de clases subrecursivas" (3 años después del resultado de BGS) que si puede separarse de entonces hay un argumento de diagonalización general para ello. Y en la práctica se han encontrado tales argumentos. Por ejemplo, los límites inferiores del espacio de tiempo de Fortnow y van Melkebeek para SAT (2000) utilizan una técnica llamada diagonalización indirecta que proporciona una diagonalización no simple.$\mathsf{NP}$$\mathsf{P}$

Entonces, ¿es incorrecta la afirmación de que la diagonalización no puede resolver vs. ? Bueno, en general, lo que los expertos entienden por diagonalización aquí es la diagonalización simple y hay una buena razón para ello.N $\mathsf{P}$$\mathsf{NP}$

Los argumentos generales de diagonalización son tan generales que realmente no tiene mucho sentido llamarlos una técnica, puede convertir fácilmente cualquier argumento de separación en un argumento de diagonalización sin mucha información: si ya tenemos alguna forma de separar dos clases de complejidad, puede elegir una función en la clase más grande, no en la más pequeña. Tome cualquier enumeración de las máquinas en la clase más pequeña. Sea cualquier máquina en la enumeración. Tenemos que definir el contraejemplo para . Pero ya sabemos que no puede resolver el problema, por lo que existe una instancia que muestra esto, define el valor de la función de diagonalización enM M $M$$M$$M$$M$ser esa instancia Esta es la vista panorámica, si desea ver los detalles, consulte el documento de Kozen.

Veraniego:

• Cuando los expertos dicen que "la diagonalización no puede resolver vs. ", lo que quieren decir es que "la diagonalización simple no puede resolver vs. ", no la general.N P P N $\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$
• La razón por la que la diagonalización simple no puede separar de es que se transfiere al marco con oráculos (en la literatura se declara como "diagonalización relativizada") y la separación no se mantiene allí.$\mathsf{NP}$$\mathsf{P}$
• La razón por la que esta transferencia de un marco sin oráculo a un marco con oráculos funciona es que la diagonalización simple se basa en la simulación de cajas negras de TM y no importa cómo funcionan las máquinas, si tiene un oráculo o no.

Dos buenos documentos para aprender más sobre la diagonalización son

• La encuesta de Lance Fortnow "Diagonalización", 2001, y
• Documento de Russell Impagliazzo, Valentine Kabanets y Antonina Kolokolova "Un enfoque axiomático para la algebrización", 2009. (Tenga en cuenta que la algebraización es una extensión de la diagonalización simple ).

Sea y dos clases de complejidad. Se dice que una separación ( ) o colapso ( ) se relativiza si para todos los oráculos tenemos o respectivamente. La prueba de Baker-Gill-Solovay nos dice que o no se relativiza.B A ≠ B A = B O A O ≠ B O A O = B O P = N P P ≠ N $\mathrm{A}$$\mathrm{B}$$\mathrm{A} \neq \mathrm{B}$$\mathrm{A} = \mathrm{B}$$\mathrm{O}$$\mathrm{A}^\mathrm{O} \neq \mathrm{B}^\mathrm{O}$$\mathrm{A}^\mathrm{O} = \mathrm{B}^\mathrm{O}$$P = NP$$P \neq NP$

¿Por qué es esto un problema? Cuando salió esta prueba, la mayoría de las técnicas y trucos que sabíamos para separar o colapsar las clases de complejidad se "relativizaron", ya que funcionan con respecto a cualquier oráculo. Por ejemplo, el teorema de la jerarquía del tiempo (así como el espacio y las versiones no deterministas del mismo) 'relativizan': prueban separaciones para clases para las cuales esta separación se relativiza, y de hecho, prueban el resultado más fuerte que la separación tiene con respecto a cualquier oráculo

Si una técnica o truco funciona independientemente de si hay un oráculo presente, entonces no es posible probar o por el argumento anterior. Esto significa que una gran cantidad de trucos y técnicas que conocemos no funcionan en este problema (o incluso en muchos problemas abiertos). También puede usarlo como un control de cordura para cualquier supuesta prueba de : verifique si la idea no se sostiene en presencia de un oráculo completo - si aún funciona, entonces está mal.P ≠ N P P ≠ N P P S P A C $P = NP$$P \neq NP$$P \neq NP$$\mathrm{PSPACE}$