Gradreduktionsschritt in Dinurs Beweis des PCP-Theorems

8

Im Gradreduktionsschritt von Dinurs Beweis wird der Eingabegraph in einen Graphen transformiert indem jeder Scheitelpunkt durch einen Satz von Scheitelpunkten, , ersetzt wird, so dass und Auferlegen eines Grad-d-Expander-Graphen auf die für alle . Dies macht einem regulären Graphen von d 1 und die Konstruktion stellt sicher, dass sich die Lücke nur um einen konstanten Faktor verringert. Ich habe mich gefragt, was passieren würde, wenn wir stattdessen jeder Wolke einen Zyklus auferlegen würden. Ich habe versucht, den Tropfen in der Lücke zu begrenzen, konnte dies aber nicht. Zerfällt der Beweis in diesem Schritt?GG′v∈V(G)cloud(v)|cloud(v)|=degreeG(v)cloud(v)v∈V(G)G′

cc.complexity-theory pcp Hsien-Chih Chang 張顯 之
quelle

Antworten:

14

Für die Konstruktion ist es wichtig, einen Expander zwischen den Kopien eines Scheitelpunkts (der "Wolke" des Scheitelpunkts) zu haben. Andernfalls können Sie nicht argumentieren, dass der Gegner, der den Scheitelpunkten Werte zuweist, besser daran ist, diesen Scheitelpunkten denselben Wert zuzuweisen.

Insbesondere wenn Sie anstelle eines Expanders einen Zyklus haben, kann der Prüfer einen Wert für einen Halbzyklus und einen Wert für den anderen Halbzyklus zuweisen. Auf diese Weise erkennt der Prüfer mit hoher Wahrscheinlichkeit nicht die Inkonsistenz zwischen den Scheitelpunkten, aber Sie können nicht auf die Solidität des Originaldiagramms zurückgreifen, um die Solidität für das neue Diagramm zu beweisen (es ist, als würde der Prüfer im Originaldiagramm zwei verwenden verschiedene Zuordnungen für den Scheitelpunkt).

Dana Moshkovitz
quelle
Das Argument schlägt also genau an dieser Stelle fehl, da wir den Soundness-Parameter oder die Lücke nicht steuern können (unter Verwendung des Soundness-Parameters für das ursprüngliche Diagramm)?
2
@Abhishek: Durch Steuern des Soliditätsparameters für das neue Diagramm steuern Sie die Lücke (= Lücke zwischen Vollständigkeit und Solidität, und die Vollständigkeit ändert sich im neuen Diagramm nicht). Stellen Sie sich einen Expander als eine kleine Annäherung an ein vollständiges Diagramm vor: Ein vollständiges Diagramm würde Sie zwingen, für alle Scheitelpunkte dieselbe Zuordnung zu verwenden.
Sasho Nikolov
2
@ Abhishek: ja.
Dana Moshkovitz
@Abhishek Wenn diese Antwort genau das ist, wonach Sie suchen (und es scheint so), sollten Sie auf das Häkchen unter der Antwortbewertung klicken, um sie zu akzeptieren.
Suresh Venkat