en términos de

15

El sistema de prueba probabilística se conoce comúnmente como una restricción de M A , donde Arthur solo puede usar f ( n ) bits aleatorios y solo puede examinar g ( n ) bits de el certificado de prueba enviado por Merlin (ver, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).PCP[f(n),g(n)]MAf(n)g(n)

Sin embargo, en 1990 Babai, Fortnow y Lund demostraron que , por lo que no es exactamente una restricción. ¿Cuáles son los parámetros ( f ( n ) , g ( n ) ) para los cuales P C P [ f ( n ) , g ( n )PAGCPAG[pagoly(norte),pagoly(norte)]=nortemiXPAGF(norte),sol(norte) ?PAGCPAG[F(norte),sol(norte)]=METROUN

Beldad
fuente

Respuestas:

18

Si desea reformular la definición de MA en términos de PCP, necesita otro parámetro para PCP, a saber, la longitud de la prueba. MA es claramente lo mismo que PCP con aleatoriedad polinómica, consultas polinómicas y pruebas de longitud polinómica. Por lo general, la longitud de la prueba en PCP no está restringida (es decir, está limitada solo implícitamente por aleatoriedad y consultas), pero esto es insuficiente para reafirmar la definición de MA.

Si está buscando alguna caracterización de la forma MA = PCP ( q ( n ), r ( n )), que no es solo la reformulación de la definición de MA, entonces no creo que se conozca dicha caracterización.

Tsuyoshi Ito
fuente
11

En virtud de un supuesto de dureza, es decir, que la clase de la complejidad requiere circuitos de tamaño exponencial, basta para derandomize M A , de modo que M A = N P . De hecho, la desrandomización es para mostrar que B P P = P (ver Impagliazzo-Wigderson o Sudan-Trevisan-Vadhan). Pero como en M A el verificador es una máquina B P P , podemos reemplazarlo con una máquina determinista.mi=reTyoMETROmi(2O(norte))METROUNMETROUN=nortePAGsiPAGPAG=PAGMETROUNsiPAGPAG

Por lo tanto, módulo esta suposición dureza, debe tener exactamente el mismo caracterización PCP como N P . La comunidad de la complejidad parece creer firmemente que la suposición de dureza también es cierta.METROUNnortePAG

Editar: También es posible que desee echar un vistazo a la tesis de maestría de Andy Drucker: "Una caracterización PCP de ": http://eccc.hpi-web.de/report/2010/019/ .UNMETRO

Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf

Sudán-Trevisan-Vadhan: http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps

Henry Yuen
fuente
11

Tsuyoshi Ito respondió la pregunta literalmente, pero quería comentar sobre la semántica de MA y PCP y cómo difieren.

MA es la versión probabilística de NP, es decir, el verificador también puede usar múltiples bits aleatorios.

En PCP podemos referirnos a la "aleatoriedad" del verificador, pero generalmente la aleatoriedad es logarítmica en el tiempo de ejecución del verificador, es decir, el verificador podría haber intentado todas las cadenas aleatorias posibles por sí mismo. En otras palabras, esta "aleatoriedad" no le da al verificador ningún poder computacional, a diferencia del caso de MA.

[Entonces, ¿para qué sirve esta "aleatoriedad"? El punto de PCP es que para la verificación probabilística es suficiente una sola prueba, con un número constante de consultas a la prueba]

Anexo (siguiendo el comentario de Tsuyoshi): En las caracterizaciones de PCP de NP, el tiempo de ejecución del verificador puede hacerse polilogármico y, de manera similar, en las caracterizaciones de NEXP, el tiempo de ejecución del verificador es polinómico. No obstante, la aleatoriedad en las construcciones de PCP generalmente se usa solo para elegir una prueba (en caracterizaciones de NP, de múltiples pruebas, y en caracterizaciones de NEXP, de exponencialmente muchas) y no para ayudar con el cálculo. Además, en MA, la prueba es de tamaño polinómico, mientras que en las caracterizaciones de NEXP, la prueba es de tamaño exponencial.

Dana Moshkovitz
fuente
Estoy de acuerdo en que solo le damos al verificador aleatoriedad logarítmica en el teorema de PCP para NP, de modo que esta aleatoriedad por sí sola no comprará al verificador ninguna potencia computacional. Sin embargo, parece que está haciendo una afirmación más general que esto al afirmar que "generalmente la aleatoriedad es logarítmica en el tiempo de ejecución del verificador", lo cual me temo que es demasiado general para ser verdad. Por lo general, no permitimos que el verificador pase tiempo exponencial incluso cuando consideramos PCP (poly, poly) = NEXP (aunque hacerlo no cambia esta igualdad), y esto parece ser un contraejemplo a su declaración.
Tsuyoshi Ito
1
¡Gracias por el seguimiento! Creo que ahora entiendo mejor lo que quiere decir al decir que MA y PCP usan la aleatoriedad de manera diferente.
Tsuyoshi Ito