cc.complexity-theory – Paso de reducción de grados en la demostración de Dinur del teorema de PCP

Pregunta:

En el paso de reducción de grados de la prueba de Dinur, el gráfico de entrada $ G $ se transforma en un gráfico $ G '$ reemplazando cada vértice $ v \ en V (G) $ por un conjunto de vértices, $ nube (v) $, tal que $ | nube (v) | = grado_G (v) $, e imponiendo un gráfico expansor de grado d en $ nube (v) $ para todos los $ v \ en V (G) $. Esto hace que $ G '$ a d + 1 gráfico sea regular, y la construcción asegura que la brecha se reduzca solo en un factor constante. Me preguntaba qué pasaría si, en su lugar, imponemos un ciclo en cada nube. Intenté limitar la caída en la brecha, pero no pude hacerlo. Entonces, ¿la prueba se rompe en este paso?

Respuesta:

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 a un medio ciclo y otro valor al otro medio ciclo. De esta manera, es muy probable que el verificador no detecte la inconsistencia entre los vértices, pero no puede apelar a la solidez del gráfico original para probar 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).

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım