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.
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.
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.
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).