¿Cuál es la razón "real" de que IP = PSPACE no es relativizante?

IP = PSPACE aparece como el ejemplo canónico de un resultado no relativizante, y la prueba de esto es que existe un oráculo tal que , mientras que para todos los oráculos . $O$ ${\sf coNP}^O \not\subseteq {\sf IP}^O$ ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ $O$

Sin embargo, solo he visto a unas pocas personas dar una explicación "directa" de por qué el resultado de ${\sf IP} = {\sf PSPACE}$ no se relativiza, y la respuesta habitual es "aritmetización". Tras la inspección de la prueba de IP = PSPACE, esa respuesta no es falsa , pero no es satisfactoria para mí. Parece que la razón "real" se remonta a la prueba de que el problema TQBF - verdadera fórmula booleana cuantificada - está completo para PSPACE; Para demostrarlo, debe demostrar que puede codificar configuraciones de una máquina PSPACE en un formato de tamaño polinómico, y (esta parece ser la parte no relativizante) puede codificar transiciones "correctas" entre configuraciones en un tamaño de polinomio fórmula booleana: utiliza un paso de estilo Cook-Levin.

La intuición que he desarrollado es que los resultados no relativizantes son los que se asoman con la esencia de las máquinas de Turing, y el paso donde se muestra que TQBF está completo para PSPACE es donde sucede esta búsqueda, y el paso de aritmetización podría Solo sucedió porque tenías una fórmula booleana explícita para aritmetizar.

Esto me parece ser la razón fundamental por la que IP = PSPACE no es relativizante; y el mantra folklórico de que las técnicas de aritmetización no se relativizan parece ser un subproducto de eso: ¡la única forma de aritmetizar algo es si tienes una fórmula booleana que codifica algo sobre TM en primer lugar!

¿Se me escapa algo? Como una pregunta secundaria, ¿significa esto que todos los resultados que usan TQBF de alguna manera tampoco se relativizan?

cc.complexity-theory interactive-proofs relativization Henry Yuen
fuente

Puede incluir puertas de oráculo en una fórmula booleana cuantificada, y luego un TQBF ^ O relativizado está completo para PSPACE ^ O, por lo que este no es el paso no relativizante.

Emil Jeřábek apoya a Monica el

Hola Emil, ¿podrías elaborar un poco más? Digamos que tengo un máquina M, y trato de llevar a cabo la misma prueba de que L (M) (el lenguaje aceptado por M) es reducible a (lo que sea que signifique). Eventualmente tendré que encontrar una fórmula booleana que exprese si dos configuraciones C, C 'de la máquina Oracle M son vecinas (para cualquiera de las dos configuraciones C, C'). ¿Cómo puedo asegurar, independientemente del oráculo, que esta fórmula booleana tenga un tamaño finito, y mucho menos un tamaño polinómico? Por ejemplo, O podría codificar el problema de detención.

{P S P A C E}^{O}

${\sf PSPACE}^O$

T B Q F^{O}

$TBQF^O$

T B Q F^{O}

$TBQF^O$

Henry Yuen

Supongo que podría retrasar esto aún más: ¿ se relativiza el teorema de Cook-Levin ? Por las mismas razones mencionadas anteriormente, no creo que lo haga. Si el teorema de Cook-Levin se relativiza determina si la prueba de integridad de PSPACE de TQBF también se relativiza.

Henry Yuen

Una fórmula QBF ^ O puede, además de los cuantificadores usuales y las conectivas booleanas, también usar una nueva puerta de entrada sin límites, llamémosla , cuya semántica es que si y sólo si la cadena pertenece al oráculo . Expresar en este lenguaje que una configuración es sucesora de otra es un ejercicio simple, ya que puede conectar el contenido de la cinta de consulta de Oracle en . (Asumo aquí que una máquina PSPACE solo puede hacer consultas polinomialmente largas).

f (x_{0}, \dots, x_{n})

$f(x_0,\dots,x_n)$

f (x_{0}, \dots, x_{n}) = 1

$f(x_0,\dots,x_n)=1$

x_{0} \dots x_{n}

$x_0\dots x_n$

O

$O$

f

$f$

Emil Jeřábek apoya a Monica el

Ya veo: usted dice que cuando relativiza la prueba de la integridad de PSPACE de TQBF, no solo relativiza las máquinas en juego, sino que también relativiza las fórmulas booleanas en sí mismas (por lo que ya no son fórmulas booleanas en sentido estricto) ) En ese caso, puedo ver por qué el paso de aritmetización se rompería. ¡Gracias! Quizás puedas escribirlo como respuesta.

Henry Yuen

Cualquier respuesta a una pregunta de la forma, "¿Cuál es la verdadera razón por la que ..." será necesariamente algo subjetiva. Sin embargo, para el caso particular de IP = PSPACE, creo que se puede hacer un caso bastante bueno de que la aritmetización es realmente la clave, al observar que si bien IP = PSPACE no se relativiza , sí se algebriza en el sentido de Aaronson y Wigderson . Como explican en su artículo, en términos generales, una inclusión de clase de complejidad algebriza si para todos los oráculos y todas las extensiones de bajo grado de ${\cal C} \subseteq {\cal D}$ ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ $A$ $\tilde A$ . En particular, muestran que la inclusión PSPACE IP algebriza, a pesar de que no se relativiza. $A$ $\subseteq$

La intuición que he desarrollado es que los resultados no relativizantes son los que se asoman con el meollo de las máquinas de Turing

Esto no es una mala intuición, pero creo que el resultado de Aaronson-Wigderson muestra que la prueba IP = PSPACE da vueltas de una manera bastante limitada, y ciertamente no de una manera lo suficientemente sofisticada como para probar P NP, ya que Aaronson y Wigderson también demostrar que se requerirán técnicas no algebrizantes para separar P de NP. $\ne$

Timothy Chow
fuente

Gracias por la referencia Déjeme ver si entiendo esto: lo que usted, y el artículo de Aaronson / Wigderson, parecen estar discutiendo es que la "aritmetización" es un paso débilmente no relativizante, y que un pequeño cambio natural en la noción de relativización (a saber, relativización algebraica) romperá esta propiedad. Dado que el resto de la prueba IP = PSPACE es relativizante (y estoy convencido de lo que Emil dijo anteriormente), eso significa que el resultado IP = PSPACE en sí mismo es muy poco relativizante, que es lo que usted dijo. ¡Muy interesante! Gracias. Necesito una forma de aceptar ambas respuestas :)

Henry Yuen

Sí, eso es básicamente correcto.

Timothy Chow el

¿Cuál es la razón "real" de que IP = PSPACE no es relativizante?

Respuestas: