Estoy interesado en cómo se prueba que una oración se relativiza. Por supuesto, probar que una oración no se relativiza es simple, como se ve en el resultado de Baker-Gill-Solovay; pero ¿cómo se prueba que una oración se relativiza, es decir, que es verdadera en relación con cualquier oráculo? ¿Existen técnicas conocidas para lograr esto para oraciones arbitrarias?
Si conoce alguna referencia que aborde esta pregunta, me gustaría saber de ellas. Gracias.
cc.complexity-theory
reference-request
relativization
Philip White
fuente
fuente
Respuestas:
Normalmente, la forma en que las personas prueban que un teorema de complejidad se relativiza es mediante el siguiente procedimiento de dos pasos:
Demuestra el teorema.
¡Observe que su prueba se relativiza! En otras palabras, que nada en la prueba cambia si todas las máquinas mencionadas en la prueba tienen acceso al mismo oráculo A.
Sí, es realmente tan simple como eso. Para hacerlo riguroso, debe reescribir toda la prueba agregando superíndices de "A" en todo el lugar. Sin embargo, en la práctica, si las personas notan este problema, por lo general solo agregarán un comentario como "este resultado se ve fácilmente relativizado".
Si la gente parece arrogante al respecto, es porque han aprendido, por experiencia, que solo ciertas técnicas (como la aritmetización) pueden causar una prueba para no relativizarse. Entonces, si su prueba no usa esas técnicas, entonces se relativiza.
(Una analogía cercana: suponga que demuestra un teorema sobre números reales, pero su prueba nunca usa nada sobre los reales que no sea el hecho de que son un campo. Entonces es suficiente tener en cuenta ese hecho, para mostrar que un teorema análogo debe ser válido para números complejos, p-adics, etc. No es necesario rehacer la prueba).
La única situación en la que se necesita más discusión es donde ni siquiera es obvio lo que significa relativizar su teorema. (Por ejemplo, ¿cuál es el mecanismo de acceso al oráculo?) Como Kaveh señaló anteriormente, no existe una operación matemática bien definida de "relativizar" un teorema de complejidad, al igual que no hay una operación matemática bien definida de "complejizar" un teorema sobre números reales. Tenga en cuenta que, en el último caso, no es suficiente reemplazar cada aparición de R por C: probablemente también necesite reemplazar x 2 por | x | 2 (en algunos lugares, ¡no en otros!) Y realice otros cambios que sean "obvios" para un matemático pero difíciles de enumerar formalmente. Del mismo modo, en teoría de la complejidad, generalmente esEs obvio lo que significa "relativizar" un teorema (es decir, ¿quién debería tener acceso a A y qué significa para ellos acceder a él?), pero en algunos casos puede ser bastante sutil. Vea aquí para más información sobre este tema.
Volviendo la pregunta, uno podría preguntar:
¿Hay algún ejemplo de un teorema de complejidad relativizante, para el cual es significativamente más difícil demostrar que el teorema se relativiza que el teorema es verdadero?
Curiosamente, ¡no puedo encontrar un solo ejemplo indiscutible (aunque tal vez alguien más pueda hacerlo)! Aquí está lo mejor que puedo hacer:
El trabajo reciente sobre computación cuántica ciega y autenticada (por Broadbent-Fitzsimons-Kashefi, Reichardt-Unger-Vazirani y otros) podría dar ejemplos. En esos casos, la situación es que no sabemos si los teoremas relativizan o no --- pero si lo hacen relativizar, entonces, ciertamente, será necesaria una nueva idea más allá de lo que hay en las pruebas existentes.
Podría decirse que otro ejemplo podría ser la auto-reducibilidad aleatoria de #P. Si le preguntaras a la mayoría de los teóricos de la complejidad por qué eso era cierto, probablemente dirían que es porque el permanente es a la vez # P completo y aleatorio auto-reducible. Eso es cierto, pero no responde a la pregunta de si #P es rsr en relación con cualquier oráculo. Bueno, resulta que #P es rsr en relación con cualquier oráculo, y ni siquiera es difícil probarlo --- pero debes dar un argumento directo usando polinomios, en lugar de apelar a las propiedades del permanente.
En la Sección 8 de mi trabajo de algebrización de Avi Wigderson , mostramos que el teorema de GMW (que NP tiene pruebas computacionales de conocimiento cero) es la algebrización. Y que realmente hicieron tomar nuevas ideas: no "drásticamente" nuevo, pero ciertamente nada que encontramos en las pruebas habituales del teorema de SMG. Por supuesto, esto es para la algebrización más que para la relativización.
Anexo: En respuesta a una pregunta adicional de la OP, no conozco ninguna técnica para demostrar que, si pudieras probar una cierta conjetura de complejidad (que aún no lo has hecho), entonces tu prueba necesariamente se relativizaría. Sí, siempre y cuando restrinja su "búsqueda de una prueba" a técnicas de relativización solamente, puede estar seguro de que, si alguna vez logra encontrar una prueba, su prueba necesariamente se relativizará. Y en la práctica, eso es a menudo lo que hace la gente (por ejemplo, porque tienen ciertas ideas sobre cómo sería una prueba y esas ideas se relativizan). Pero no conozco ninguna forma de garantizar, a priori , que al ampliar su búsqueda para incluir técnicas no relativizadoras, no pueda encontrar una prueba que se le haya escapado antes.
fuente