Twierdzenie PCP - etap redukcji alfabetu

To, co następuje, może wydawać się głupie (i to prawdopodobnie odzwierciedla moje słabe zrozumienie - więc proszę o wyrozumiałość)

Miałem zapytanie dotyczące twierdzenia PCP. Wiemy, że po pierwszych trzech krokach mianowicie. Redukcja stopnia, ekspansja i amplifikacja odstępów , mamy wykres ograniczeń z ulepszoną przerwą i dużym rozmiarem alfabetu (jak Σ d t ). Ten problem rozwiązuje krok redukcji alfabetu.$G$$\Sigma^{d^t}$

Moje pytanie jest takie, jak zostało to przedstawione w notatkach wykładowych Venkata Guruswamiego Wprowadzenie do kompozycji , wydaje mi się, że głównym pomysłem jest wyrażenie ograniczenia ponad krawędzią e jako ograniczenia boolowskiego względem zmiennych boolowskich. Samo to niczego nie osiąga i na tej krawędzi musimy również zastosować redukcję PCP, P e . To „wygląda jak” rekursywne wywołanie PCP i tutaj zaczynam się trochę martwić. Wygląda na to, że to rekurencyjne wywołanie ponownie wysadziłoby rozmiar alfabetu.$c_e$$e$$P_e$

Autorzy przedstawili pewne wyjaśnienie, zauważając, że ta rekurencja ma „przypadek podstawowy” - mianowicie - „wewnętrzna” redukcja PCP dotyczy tylko ograniczeń o stałym rozmiarze.

$c_e$

Mam nadzieję, że moje zapytanie (tak głupie, jak jest) jest prawdopodobnie jasne. Daj mi znać, jakiej istotnej części brakuje mi (lub źle zrozumiałem).

Pytasz o dowód Dinura na twierdzenie PCP. Krok redukcji alfabetu wykorzystuje PCP, ale PCP ma bardzo różne parametry od tego, który konstruujesz, i niekoniecznie musisz użyć rekurencji, aby go zbudować. W szczególności, zgodnie z dowodem Dinura, ponieważ ten wewnętrzny PCP do redukcji alfabetu jest stosowany na wejściach o stałej wielkości, nie obchodzi nas, czy ma on ogromny (powiedzmy wykładniczy, a nawet większy) wybuch, co sprawia, że ​​stosunkowo łatwo jest dać bezpośrednia konstrukcja wystarczająco dobrego PCP.

Cały dowód, w tym ten etap, jest opisany w kilku miejscach (patrz odpowiedź na to pytanie ), więc możesz znaleźć inny opis, który ci się bardziej podoba. W szczególności w moim podręczniku złożonym z Sanjeev Arora, który jest omawiany w rozdziałach 11 i 22, oferujemy tam dwa alternatywne sposoby osiągnięcia kroku redukcji alfabetu. Jeden używa PCP opartego na Hadamard w tekście głównym. Ale może najprostszym samodzielnym wariantem jest konstrukcja opracowana w ćwiczeniu 22.5. W sekcji 22.2.1 mamy również tabelę, która dokładnie pokazuje, jaki krok dowodu ma wpływ na rozmiar alfabetu (i inne parametry, takie jak błąd poprawności, rozmiar i liczba zapytań) i która może rozwiać twoje obawy.