¿Los buenos PCP para NP nos dan buenos PCP para toda la jerarquía polinómica?

El teorema de PCP establece que cada problema de decisión en NP tiene pruebas probabilísticamente comprobables (o de manera equivalente, que existe un sistema de prueba completo y cuasi-sonoro para teoremas en NP que usa complejidad de consulta constante y logarítmicamente muchos bits aleatorios).

La "sabiduría popular" que rodea el teorema de PCP (ignorando por un momento la importancia de PCP para la teoría de la aproximación) es que esto significa que las pruebas escritas en lenguaje matemático estricto se pueden verificar de manera eficiente con cualquier grado deseado de precisión sin el requisito de leer todo prueba (o gran parte de la prueba en absoluto).

No puedo ver esto del todo. Considere la extensión de segundo orden a la lógica proposicional con uso ilimitado de cuantificadores (que me han dicho que ya es más débil que ZFC, pero no soy lógico). Ya podemos comenzar a expresar teoremas que no son accesibles para NP alternando cuantificadores.

Mi pregunta es si existe una forma simple y conocida de cuantificar 'desenrollar' los enunciados proposicionales de orden superior para que los PCP para teoremas en NP se apliquen igualmente bien a cualquier nivel de PH. Es posible que esto no se pueda hacer, que desenrollar un cuantificador cuesta, en el peor de los casos, una parte constante de la solidez o corrección de nuestro sistema de prueba.

lo.logic pcp polynomial-hierarchy Ross Snider
fuente

Me parece que un PCP para un problema casi por definición coloca el problema en BPP, lo que significa que está en por Sipser – Gács – Lautemann. Pero tal vez también vea esta pregunta relacionada .

Σ_{2} \cap Π_{2}

$\Sigma_2 \cap \Pi_2$

Peter Shor

Esto suena razonable, pero estoy confundido. Si esto fuera correcto, ¿no pondría NP en BPP?

Ross Snider

Ups Debería haber dicho MA, que también está contenido en .

Σ_{2} \cap Π_{2}

$\Sigma_2 \cap \Pi_2$

Peter Shor

Esto no funcionará. El PH es resistente a los lemmas involucrados. considere algo como EXP ^ 2. Puede manejar RP, RNP, etc. como una broma. No estás viajando por esa jerarquía fácilmente.

Steve Uurtamo

Respuestas:

La verdad de una declaración es diferente de tener una prueba (corta) en un sistema de prueba. El lenguaje es expresivo, pero no significa que todas las declaraciones válidas en el idioma tengan pruebas cortas en el sistema.

El teorema no dice que puede verificar la verdad de una declaración o incluso la exactitud de una prueba larga arbitraria o de teoremas arbitrarios. Es para pruebas de membresía en un conjunto , que por definición tienen pruebas de tamaño polinomiales (certificados) de membresía. El teorema solo dice que no es necesario leer la prueba de pertenencia completa (tamaño polinómico) en un conjunto para decidir su corrección. $\mathsf{NP}$ $\mathsf{NP}$

Una implicación del teorema es aplicarlo al conjunto de teoremas en un lenguaje arbitrario que tiene pruebas cortas (es decir, un polinomio arbitrario) en un sistema de prueba eficiente (es decir, es decidible en el tiempo polinómico si una cadena dada es una prueba de un determinado declaración). Por ejemplo, teoremas de ZFC que tienen pruebas de tamaño donde es el tamaño de la fórmula. Si el sistema de prueba es sólido, entonces puede verificar probabilísticamente la corrección de los teoremas que tienen pruebas cortas con la lectura de una pequeña parte de sus pruebas. Creo que este es el significado de la declaración informal "las pruebas escritas en lenguaje matemático estricto se pueden verificar de manera eficiente con cualquier grado deseado de precisión sin el requisito de leer la prueba completa ". $n^{100}$ $n$

Kaveh
fuente

Déjame intentar aclarar.

Considere el siguiente problema computacional: dada una declaración matemática (en su sistema de axiomas favorito) y un número n dado en representación unaria, decida si la declaración tiene una prueba de tamaño n.

Este es un problema NP: dada una prueba, uno puede verificar eficientemente que es de tamaño ny que es una prueba válida del teorema. Nota: incluso si el enunciado involucra cuantificadores como FOR ALL, no significa que el verificador necesite verificar todas las posibilidades, solo significa que el verificador usa reglas de inferencia que involucran el cuantificador FOR ALL.

Por lo tanto, el teorema de PCP se aplica a este problema, por lo que hay un formato de prueba (diferente) que permite la verificación probabilística.

Otra nota (con respecto al comentario de Peter): el verificador PCP usa solo aleatoriedad logarítmica. Esto significa que podría ser reemplazado por un verificador estándar, determinista, que examina la prueba completa. Es decir, tener un verificador PCP para un idioma lo pone en NP.

Dana Moshkovitz
fuente