Pruebas interactivas para niveles de la jerarquía polinómica.

33

Sabemos que si tiene una máquina PSPACE, es lo suficientemente potente como para proporcionar una prueba interactiva de cualquier nivel de la jerarquía polinómica. (Y si recuerdo bien, todo lo que necesita es #P.) Pero suponga que desea dar una prueba interactiva de membresía en un idioma . ¿Es suficiente poder resolver problemas en ? ¿Es adecuado resolver problemas en ? En términos más generales, si puede resolver los problemas o , ¿para qué es suficiente para generar pruebas interactivas de todos los idiomas en ? $\Sigma_2$ $\Sigma_2$ $\Sigma_5$ $\Sigma_k$ $\Pi_k$ $\Sigma_\ell$ $\Sigma_\ell$

Esta pregunta se inspiró en esta pregunta de intercambio de pila teoría .

cc.complexity-theory interactive-proofs Peter Shor
fuente

¿Solo le interesa el caso de un solo probador o le interesa el caso de varios probadores? Me parece que la forma obvia de atacar esto sería a través de PCP, que podría ser sencillo para dos probadores, pero probablemente no funcionará para un solo probador.

Joe Fitzsimons

1

Estaría interesado en ambos casos. Me he preguntado acerca de esta pregunta para los probadores individuales durante bastante tiempo, pero no había pensado en absoluto en los probadores múltiples.

Peter Shor

44

@Peter: Al revisar el documento IP = PSPACE, parece que la prueba se llevaría a cabo utilizando

(que está completo para

) en lugar de QBF, siempre que tenga un probador lo suficientemente potente como para calcular las identidades polinómicas derivadas de La aritmitización del

. ¿Me estoy perdiendo de algo?

{QBF}_{k}

$\mbox{QBF}_k$

Σ_{k}^{P}

$\Sigma^P_k$

{QBF}_{k}

$\mbox{QBF}_k$

Joe Fitzsimons

1

@ Joe, no he considerado esa idea; podría funcionar.

Peter Shor

2

Joe, tal vez deberías publicarlo como respuesta

Suresh Venkat

25

Incluso para dar una IP para coNP, usando las técnicas actuales, uno necesita aritmetizar, es decir, usar el conteo, lo que significa esencialmente toda la potencia de #P. Creo que cualquier probador más débil, incluso para coNP, sería muy interesante (en particular, implicaría una nueva técnica no relativa).

Noam
fuente

@ Peter: Noam tiene razón. Cito las siguientes líneas desde aquí : ... basar el hashing resistente a colisiones en la peor dureza de NP a través de una reducción de caja negra implica un sistema de prueba interactivo para co-NP con el probador en BPP ^ NP ... Todos conocidos (incluso multiprover) los sistemas de prueba para co-NP requieren probadores con complejidad #P ...

MS Dousti

En cuyo caso, mi respuesta probablemente sea una tontería. Gracias por señalar esto.

Joe Fitzsimons

En realidad, esto es realmente interesante, dado que una prueba interactiva para el no isomorfismo gráfico solo necesita un probador con un oráculo para ese problema. Parece una evidencia de que GI es muy muy débil (como en P) o que los límites para las pruebas interactivas de los niveles de la jerarquía polinómica son muy flojos.

Joe Fitzsimons

1

Supongo que no se sabe que varios probadores ayuden. ¿Es esto correcto?

Peter Shor

1

@Joe La prueba para el no isomorfismo gráfico es una prueba de moneda pública redonda constante, por lo que la coloca en la clase AM (se cree ampliamente que es igual a NP, y por lo tanto se cree que GI y GNI están en

). Esto es mucho más bajo que la prueba redonda polinómica que se cree que es necesaria para probar la membresía en problemas completos de coNP.

N P \cap c o N P

$NP \cap coNP$

Boaz Barak

21

Este es un problema abierto (maravilloso) conocido en el que he trabajado de vez en cuando sin éxito.

Avi Wigderson y yo mencionamos el problema en nuestro documento de algebrización , donde planteamos la cuestión de si las contenciones como coNP ⊆ IP _NP pueden demostrarse mediante técnicas de algebrización. (Aquí IP _NP denota IP con un verificador BPP y un comprobador BPP ^NP .) Si (como conjeturo) la respuesta es no, entonces eso proporcionaría una razón formal por la cual cualquier protocolo interactivo como el que Peter solicita requeriría no relativizar técnicas que van "fundamentalmente más allá" de las utilizadas para IP = PSPACE.

Una pregunta análoga es si BQP = IP _BQP , donde IP _BQP significa IP con un verificador BPP y un comprobador BQP (tiempo polinómico cuántico). Esa pregunta también está abierta, aunque un avance reciente de Broadbent, Fitzsimons y Kashefi mostró que una afirmación estrechamente relacionada es cierta.

Scott Aaronson
fuente

20

Sí, la pregunta de si coNP tiene una prueba interactiva donde el probador es más débil que #P (por ejemplo, polytime con acceso al oráculo NP) es una pregunta abierta bien conocida. El siguiente artículo reciente de Haitner, Mahmoody y Xiao discute esta pregunta y muestra algunas consecuencias del supuesto de que esto no se puede hacer.

Boaz Barak
fuente

11

Como Suresh me sugirió que publique mi comentario como respuesta, lo haré. Sin embargo, no considero que esto constituya una respuesta completa ya que no he intentado probar esto, y puede llegar a ser un callejón sin salida.

$\mbox{QBF}_k$ $\Sigma^P_k$ $\mbox{QBF}_k$ $\Sigma^P_k$

Joe Fitzsimons
fuente

el problema ya surge en la prueba de coNP. El protocolo sumcheck tiene n rondas (una para cada variable). En cada ronda, el probador necesita obtener los coeficientes del polinomio que se obtiene mediante una suma exponencialmente grande. No sé cómo hacerlo con menos potencia que #P.

Boaz Barak

@Boaz: Sí, creo que este enfoque está destinado a fracasar. Pensé que había visto una versión de la aritmetización realizada en algún lugar de tal manera que el polinomio solo tomaba valores 1 o 0 para entradas de 0s y 1s. Si este es el caso, parece que podría usar un oráculo para un problema de decisión correspondiente. Por otra parte, ¡tal vez lo haya imaginado!

Joe Fitzsimons

Pruebas interactivas para niveles de la jerarquía polinómica.

Respuestas: