Teorema PCP - Langkah Pengurangan Alfabet

Berikut ini mungkin tampak bodoh (dan itu mungkin mencerminkan pemahaman saya yang buruk - jadi tolong tahan dengan saya)

Saya punya pertanyaan tentang teorema PCP. Kita tahu bahwa setelah tiga langkah pertama yaitu. Pengurangan Gelar, Ekspanderisasi dan Penguatan Gap, kami memiliki grafik kendala dengan kesenjangan yang ditingkatkan dan ukuran alfabet besar (seperti ). Ini adalah masalah yang alamat langkah pengurangan alfabet.Σ d $G$$\Sigma^{d^t}$

Pertanyaan saya adalah bahwa sebagaimana diuraikan dalam catatan kuliah Venkat Guruswami, Pengantar Komposisi , bagi saya tampaknya gagasan tingkat tinggi adalah untuk mengekspresikan kendala pada batas sebagai kendala Boolean atas variabel boolean. Ini dengan sendirinya tidak mencapai apa-apa dan kita juga perlu menerapkan pengurangan PCP, , di tepi ini. Ini "seperti" permohonan PCP rekursif dan di sinilah saya mulai sedikit khawatir. Sepertinya doa rekursif ini akan meledakkan ukuran alfabet lagi. e P $c_e$$e$$P_e$

Para penulis telah menawarkan beberapa penjelasan dengan mengamati bahwa rekursi ini memiliki "kasus dasar" - yaitu - pengurangan PCP "dalam" hanya berlaku untuk kendala ukuran konstan.

(Dengan ini saya mengerti bahwa rekursi dalam dipanggil hanya ketika kita melihat kendala atas satu sisi yang merupakan kendala biner, tapi masih saya belum menemukan ketakutan bahwa entah bagaimana kita masih bisa meledakkan ukuran alfabet sebagai gantinya menyusutnya). Bagi saya, masih tampak bahwa pengulangan langkah Amplifikasi Gap secara rekursif hanya akan memperburuk masalah dengan meledakkan ukuran alfabet kecuali jika kita memasukkan langkah-langkah untuk menangani kasus dasar sedikit berbeda.$c_e$

Saya harap pertanyaan saya (sebodoh itu) mungkin jelas. Tolong beri tahu saya bagian penting apa yang saya lewatkan (atau salah pahami).

Anda bertanya tentang bukti Dinur tentang Teorema PCP. Langkah pengurangan alfabet memang menggunakan PCP, tetapi PCP memiliki parameter yang sangat berbeda dari yang Anda buat, dan Anda tidak harus menggunakan rekursi untuk membuatnya. Secara khusus, dalam bukti Dinur, karena PCP bagian dalam ini untuk pengurangan alfabet diterapkan pada input berukuran konstan, kami tidak peduli apakah itu memiliki ledakan besar (katakanlah eksponensial atau bahkan lebih dari itu), yang membuatnya relatif mudah untuk memberikan konstruksi langsung dari PCP yang cukup baik.

Seluruh bukti termasuk tahap ini dijelaskan di beberapa tempat (lihat jawaban untuk pertanyaan ini ), sehingga Anda dapat menemukan deskripsi berbeda yang lebih Anda sukai. Secara khusus, dalam buku teks kompleksitas saya dengan Sanjeev Arora ini dibahas dalam Bab 11 dan 22, kami menawarkan dua cara alternatif untuk mencapai langkah pengurangan alfabet. Salah satunya adalah menggunakan PCP berbasis Hadamard dalam teks utama. Tetapi mungkin varian mandiri yang paling sederhana adalah konstruksi yang dikerjakan di Latihan 22.5. Kami juga memiliki tabel, di Bagian 22.2.1, yang menunjukkan dengan tepat apa yang dilakukan langkah pembuktian terhadap ukuran alfabet (dan parameter lain seperti kesalahan kesehatan, ukuran dan jumlah kueri) dan yang dapat menghilangkan kekhawatiran Anda.