¿Se pueden usar los resultados de la relativización para probar oraciones formalmente independientes?

12

¿Es posible demostrar que una oración debe ser formalmente independiente basada en el hecho de que no es relativizante? En otras palabras, ¿hay ejemplos de oraciones en la teoría de la computabilidad / complejidad donde se pueda demostrar tanto a) que todas las pruebas que resuelven la cuestión de si dos clases son iguales o no deben relativizarse, yb) que no hay pruebas relativizantes que se puede usar en tal resolución?

Creo que sería más fácil obtener resultados que satisfagan la parte b. Otra forma de hacer esta pregunta es: ¿Alguna vez ha habido una oración en la teoría de la computabilidad o la complejidad en la que se pueda demostrar que la igualdad o la desigualdad deben establecerse mediante el uso de (y solo mediante el uso de) técnicas de relativización? Un ejemplo de esto sería interesante para mí.

Gracias; Una respuesta a cualquiera de las versiones de esta pregunta sería muy interesante para mí.

-Philip

Philip White
fuente

Respuestas:

18

No existen preguntas "naturales" de teoría de la complejidad que hayan demostrado ser independientes de sistemas formales realmente poderosos, como la teoría de conjuntos ZF o la aritmética de Peano. (Ciertamente, uno podría construir esa pregunta artificialmente, jugando juegos con oraciones de Gödel).

Por otro lado, sí, puede interpretar la afirmación de que una oración S se relativiza como que significa que S puede probarse a partir de un cierto conjunto restringido de axiomas (básicamente, los "axiomas de Cobham" que caracterizan el cierre bajo reducciones de tiempo polinomial). Por el contrario, la existencia de oráculos que hacen que S sea verdadero o falso es equivalente a que S sea independiente de esos axiomas particulares. Aquí está el documento para leer sobre esto, por Arora, Impagliazzo y Vazirani.

Esta es una conexión muy bonita matemáticamente --- pero vale la pena destacar que hacerlo tienen técnicas (como aritmetización) que van fuera de los axiomas relativizando. Y no conozco ningún resultado de la forma "si el problema abierto natural P puede resolverse, entonces también puede resolverse de forma relativizante".

Scott Aaronson
fuente
44
Creo que Impagliazzo-Kabanets-Kolokolova extendió Arora-Impagliazzo-Vazirani a la aritmetización en STOC 2009: dx.doi.org/10.1145/1536414.1536509
Joshua Grochow