Paso de reducción de grado en la prueba de Dinur del teorema de PCP

8

En el paso de reducción de grados de la prueba de Dinur, el gráfico de entrada se transforma en un gráfico G ' reemplazando cada vértice v V ( G ) por un conjunto de vértices, c l o u d ( v ) , de modo que | c l o u d ( v ) | = d e g r e e G ( v ) , e imponiendo un gráfico expansor de grado d en c l oGGvV(G)cloud(v)|cloud(v)|=degreeG(v) para todos v V ( G ) . Esto hace que G ' a d + 1 sea un gráfico regular, y la construcción asegura que la brecha se reduzca solo en un factor constante. Me preguntaba qué pasaría si impusiéramos un ciclo en cada nube. Traté de limitar la caída en la brecha, pero no pude hacerlo. Entonces, ¿la prueba se rompe en este paso?cloud(v)vV(G)G

Hsien-Chih Chang 張顯 之
fuente

Respuestas:

14

Es esencial para la construcción tener un expansor entre las copias de un vértice (la "nube" del vértice). De lo contrario, no podrá argumentar que el adversario que asigna valores a los vértices está mejor asignando a esos vértices el mismo valor.

En particular, si en lugar de un expansor tiene un ciclo, el probador puede asignar un valor de medio ciclo a un valor, y el otro medio ciclo a otro valor. De esta manera, con una buena probabilidad, el verificador no detectará la inconsistencia entre los vértices, pero no puede apelar a la solidez del gráfico original para demostrar la solidez del nuevo gráfico (es como permitir que el probador en el gráfico original use dos diferentes asignaciones para el vértice).

Dana Moshkovitz
fuente
Entonces, ¿el argumento falla precisamente en este punto ya que no podemos controlar el parámetro de solidez o la brecha (usando el parámetro de solidez para el gráfico original)?
2
@Abhishek: controlar el parámetro de solidez para el nuevo gráfico es cómo se controla la brecha (= brecha entre la integridad y la solidez, y la integridad no cambia en el nuevo gráfico). Piense en un expansor como una aproximación de pequeño grado de un gráfico completo: un gráfico completo lo obligaría a usar la misma asignación para todos los vértices.
Sasho Nikolov
2
@Abhishek: sí.
Dana Moshkovitz
@Abhishek si esta respuesta es lo que está buscando (y parece que lo es), debe hacer clic en la marca de verificación debajo del puntaje de respuesta para aceptarla.
Suresh Venkat