Ejemplo para un verificador PCP no trivial para un problema NP-Complete

Question

Durante mi participación en un curso sobre cómo lidiar con problemas difíciles de NP, he encontrado el teorema de PCP, declarando

$ qquad displaystyle mathsf {np} = mathsf {pcp} ( log n, 1) $.

Entiendo la definición técnica de un verificador de PCP, por lo que sé, en principio, qué tipo de algoritmo debe existir para cada problema de NP: un algoritmo aleatorizado que verifica $ O (1) $ bits del certificado dado para la entrada dada usando $ o ( log n) $ bits aleatorios, de modo que este algoritmo es esencialmente un verificador de error unilateral de Monte-Carlo.

Sin embargo, tengo problemas para imaginar cómo tal algoritmo puede lidiar con un problema de NP-completado. A falta de leer la prueba del teorema de PCP, ¿hay ejemplos concretos para tales algoritmos?

Hice las secciones relevantes de Complexidad computacional: un enfoque moderno por Arora y Barak (2009) pero no encontró ninguno.

Un ejemplo que usa un $ mathsf {pcp} ( _, ll n) $ algoritmo estaría bien.

Answer 1

Siguiendo un comentario de sdcvvc Revisé el ejemplo 11.7 en Complexidad computacional: un enfoque moderno por Arora y Barak (Reclutar de 2008). Allí, los autores describen un "algoritmo de PCP" para el problema Gráfico no isomorfismo (GNI):

Aporte: Dos gráficos $ g_0 $ y $ g_1 $ con $ n $ vértices cada uno.

Producción: Acepte si y solo si $ g_0 $ y $ g_1 $ no son isomorph (escriba $ g_0 no equiv g_1 $).

Denotamos el certificado (lo llaman "prueba") por $ pi $ y con $ pi (i) $ el $ i $ -th bit de $ pi $.

El algoritmo $ A $ procede de la siguiente manera:

• Elija un poco $ b in {0,1 } $ uniformemente al azar.
• Elija una permutación $ Sigma en S_N $ (de los vértices de $ g_b $).
• Acepte si $ pi ( langle sigma (g_b) rangle) = b $, rechazar lo contrario.

Aquí, $ langle _ rangle $ es una biyección computable de $ mathbb {n}^n $ a un rango adecuado $ [0..n] subseteq mathbb {n} $. Suponemos que si el bit desactivado en $ pi $ no existe, es decir, el certificado es demasiado corto, rechazamos.

Reclamar: Por algoritmo anterior, GNI está en $ operatorname {PCP} (n log n, 1) $, es decir

1. El algoritmo usa $ o (n log n) $ bits y consultas aleatorias $ o (1) $ bits de $ pi $,
2. $ (G_0, g_1) in mathrm {gni} $ implica que hay algún certificado $ pi $ para que $ pr [a (g_0, g_1, pi) text {acepta}] = 1 $, y
3. $ (G_0, g_1) noin mathrm {gni} $ implica que $ pr [a (g_0, g_1, pi) text {rechazos}] geq tfrac {1} {2} $ todos certificados $ pi in {0,1 }^*$.

AD 1: Borre del algoritmo observando que el muestreo de permutación uniforme es posible con $ aprox n log n $ bits aleator.

Ad 2: Considere el certificado

$ qquad displayStyle pi ( langle h rangle) = begin {casos} 0 &, h equiv g_0, h no equiv g_1 1 &, h mec_1, h no equiv g_0 text {arbitrary} &, text {de lo contrario} end {casos} $

donde $ H $ son todos gráficos con $ n $ nodos. Dado que $ g_0 no equiv g_1 $ y $ sigma (g_b) equiv g_b $, tenemos $ sigma (g_b) no equiv g_ {1-b} $ por todos $ b $ y $ sigma $ . La consulta a $ pi $, por lo tanto, siempre produce $ B $ y, por lo tanto, siempre acepta.

Ad 3: Deje $ pi in {0,1 }^*$ arbitrary y $ h = sigma (g_b) $ el gráfico de consulta elegida. Si nuestra consulta golpea un poco de $ pi $, rechazamos por suposición, lo cual es correcto. De lo contrario, calculamos

$ qquad begin {align} pr [ text {aceptar}] & = pr [b = 0] cdot frac {#[ pi (h) = 0 mid h equiv g_0]} { #[H Equiv g_0]} + pr [b = 1] cdot frac {#[ pi (h) = 1 mid h equiv g_1]} {#[h mec_1]} & = frac {1} {2} cdot left ( frac {#[h) frac {#[ pi (h) = 1 mid h equiv g_0]} {#[h equiv g_0]} right) & = frac {1} {2} end {align} $ usando ese $ h equiv g_1 iff h equiv g_0 $ en este caso.

Por lo tanto, el reclamo está probado.

---

Algunas observaciones que me ayudaron a comprender mejor estos conceptos.

• El certificado $ pi $ puede ser arbitrariamente largo y arbitrariamente complejo. Tenga en cuenta que los certificados "buenos" para el algoritmo anterior resuelven esencialmente el mismo problema que el algoritmo (muchas veces).
• Pero eso no implica que ningún problema de decisión se pueda resolver en el estilo PCP "solo proporcionando la respuesta en el certificado". La condición 3 evita cualquier intento ingenuo de ese tipo.
• En general, no es posible derivar un algoritmo eficiente (error unilado aleatorio) que adivina el certificado (como es el caso de los verificadores de certificados NP).

---

1. Estrictamente hablando, esto supone que $ n! = 2^k $ (que por supuesto casi nunca se mantiene) ya que nosotros tener un tiempo de ejecución infinito en el peor de los casos por otros $ n $. Sin embargo, Arora/Barak parece ignorar este aspecto.

Answer 2

Dos problemas que podrían ayudar a desarrollar la intuición:

1. Demuestre que $ mathsf {am} subseteq mathsf {pcp} ( text {poly} (n), 1) $. Se le permite asumir $ mathsf {np} subseteq mathsf {pcp} ( text {poly} (n), 1) $.

2. Demuestre que $ mathsf {pspace} subseteq mathsf {pcp} ( text {poly} (n), text {poly} (n)) $. Insinuación:

Usar IP = PSPACE

Trivia: el primer ejercicio subsume el PCP para GNI, mientras que el segundo subsume el PCP para permanente. Ambos resultados están subsumidos por $ Mathsf {nexp} = mathsf {pcp} ( text {poly} (n), 1) $.