Técnicas para probar que una oración relativiza

8

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.

Philip White
fuente
¿No es suficiente tener una prueba de la oración que funciona en relación con todos los oráculos? Un ejemplo típico serán los teoremas de jerarquía.
Sasho Nikolov
No estoy seguro. ¿Qué sucede si no está seguro de si la oración es verdadera, pero le gustaría saber si la oración se relativizaría si fuera verdad?
Philip White
¿Cuál es la definición de "oración relativiza"? ¿Qué quiere decir con "técnicas para lograr esto para oraciones arbitrarias"?
Kaveh
1
Bueno, supongo que probarlo en relación con cualquier oráculo sigue siendo una técnica :) Me pregunto si conocemos algún ejemplo de una proposición sobre TM que no esté probada pero se sepa que es verdadera o falsa en relación con cualquier oráculo (eso es lo que usted ¿verdad? Como dijo Kaveh, algo de formalización ayudaría)
Sasho Nikolov
1
@Kaveh, quiero decir una declaración matemática que (presumiblemente) hace referencia a las máquinas de Turing. La declaración "se relativiza" si, en el caso de que agreguemos un oráculo para una máquina de Turing, la declaración sigue siendo verdadera o falsa.
Philip White

Respuestas:

12

Normalmente, la forma en que las personas prueban que un teorema de complejidad se relativiza es mediante el siguiente procedimiento de dos pasos:

  1. Demuestra el teorema.

  2. ¡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:

  1. 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.

  2. 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.

  3. 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.

Scott Aaronson
fuente
Eché un vistazo a la sección 8 de tu artículo y estoy perplejo al final de la página 40. ¿Cómo da el comprobador pruebas de conocimiento cero para las partes (1) a (4)? Incluso "las cláusulas estándar están satisfechas" implica que el oráculo verifique la validez de las liberaciones. Si bien puede preverse la recursión, no está claro para mí que la recursividad pueda alcanzar un conjunto suficientemente pequeño de casos básicos.
(Ahora para un asunto tangente menor). ¿Sabes si los resultados positivos de este artículo en el modelo de bits ocultos (y una versión modificada), como resumí en el párrafo de 6 líneas en el medio de esta respuesta , algebrize? A diferencia del SAT, no veo ninguna forma de relativizar o algebrizar el ciclo Ham dirigido.
Los comentarios de @RickyDemer no están indexados por las funciones de búsqueda, y no se recomiendan para largas discusiones o nuevas preguntas y respuestas. Puede valer la pena crear una pregunta por separado (con un enlace a esta respuesta) aquí o en CS.SE en función de sus comentarios y luego Scott u otros usuarios pueden abordarlos en un asunto que esté más en línea con la mecánica del sitio.
Artem Kaznatcheev