PCP-Theorem - Alphabet-Reduktionsschritt

Was folgt, mag dumm erscheinen (und das spiegelt wahrscheinlich mein schlechtes Verständnis wider - bitte nehmen Sie es mit mir auf)

Ich hatte eine Frage zum PCP-Theorem. Wir wissen, dass nach den ersten drei Schritten nämlich. Gradreduzierung, Expanderisierung und Lückenverstärkung, wir haben einen Beschränkungsgraphen mit verbesserter Lücke und großer Alphabetgröße (wie Σ d t ). Es ist dieses Problem, das im Alphabet-Reduktionsschritt behoben wird.$G$$\Sigma^{d^t}$

Meine Frage ist, dass, wie in Venkat Guruswamis Vorlesungsunterlagen Einführung in die Komposition dargelegt , die Idee auf hoher Ebene darin besteht, die Einschränkung über einer Kante e als boolesche Einschränkung über boolesche Variablen auszudrücken . Dies allein bringt nichts und wir müssen auch die PCP-Reduktion P e auf diese Kante anwenden . Dies "sieht aus wie" ein rekursiver Aufruf von PCP und hier mache ich mir ein wenig Sorgen. Es scheint, als würde dieser rekursive Aufruf die Alphabetgröße wieder in die Luft jagen.$c_e$$e$$P_e$

Die Autoren haben einige Erklärungen abgegeben, indem sie festgestellt haben, dass diese Rekursion einen "Basisfall" hat - nämlich - die "innere" PCP-Reduktion gilt nur für Einschränkungen konstanter Größe.

(Darunter verstehe ich, dass die innere Rekursion nur aufgerufen wird, wenn wir Einschränkungen über eine einzelne Kante betrachten, die eine binäre Einschränkung ist, aber ich bin noch nicht über die Befürchtung hinweggekommen, dass wir die Alphabetgröße irgendwie immer noch in die Luft jagen könnten anstatt es zu verkleinern). Mir scheint es immer noch, dass eine rekursive Wiederholung des Gap Amplification-Schritts die Sache nur verschlimmert, indem die Alphabetgröße vergrößert wird, es sei denn, wir integrieren Maßnahmen, um den Basisfall ein wenig anders zu behandeln.$c_e$

Ich hoffe, meine Frage (so albern sie auch ist) ist wahrscheinlich klar. Bitte lassen Sie mich wissen, welchen wesentlichen Teil ich vermisse (oder missverstanden habe).

Sie fragen nach Dinurs Beweis des PCP-Theorems. Der Alphabet-Reduktionsschritt verwendet zwar einen PCP, der PCP hat jedoch ganz andere Parameter als der von Ihnen erstellte, und Sie müssen nicht unbedingt die Rekursion verwenden, um ihn zu erstellen. Insbesondere in Dinurs Beweis ist es uns egal, ob dieser innere PCP für die Alphabetreduktion auf Eingaben konstanter Größe angewendet wird, ob er eine große (z. B. exponentielle oder sogar mehr) Explosion aufweist, was es vergleichsweise einfach macht, eine zu geben direkter Aufbau eines ausreichend guten PCP.

Der gesamte Beweis einschließlich dieser Phase wird an mehreren Stellen beschrieben (siehe Antwort auf diese Frage ), sodass Sie möglicherweise eine andere Beschreibung finden, die Ihnen besser gefällt. Insbesondere in meinem Komplexitätslehrbuch mit Sanjeev Arora, das in den Kapiteln 11 und 22 behandelt wird, bieten wir dort zwei alternative Möglichkeiten an, um den Schritt der Alphabetreduzierung zu erreichen. Eine davon ist die Verwendung von Hadamard-basiertem PCP im Haupttext. Aber die vielleicht einfachste eigenständige Variante davon ist die in Übung 22.5 erarbeitete Konstruktion. Wir haben auch eine Tabelle in Abschnitt 22.2.1, die genau zeigt, was genau der Schritt des Beweises mit der Alphabetgröße (und anderen Parametern wie Soliditätsfehler, Größe und Anzahl der Abfragen) macht und die Ihre Bedenken zerstreuen kann.