Langkah pengurangan derajat dalam bukti Dinur tentang teorema PCP

8

Pada langkah reduksi derajat dari bukti Dinur, grafik input ditransformasikan menjadi grafik G dengan mengganti setiap simpul v V ( G ) dengan seperangkat simpul, c l o u d ( v ) , sedemikian rupa sehingga | c l o u d ( v ) | = d e g r e e G ( v ) , dan memaksakan derajat d grafik expander pada c l oGGvV(G)clHaikamud(v)|clHaikamud(v)|=degreeG(v) untuk semua v V ( G ) . Ini membuat G a d + 1 grafik reguler, dan konstruksi memastikan bahwa celah hanya berkurang oleh faktor konstan. Saya bertanya-tanya apa yang akan terjadi jika kita memaksakan siklus pada setiap cloud sebagai gantinya? Saya mencoba membatasi drop di celah, tetapi tidak dapat melakukannya. Jadi, apakah buktinya rusak pada langkah ini?clHaikamud(v)vV(G)G

Hsien-Chih Chang 張顯 之
sumber

Jawaban:

14

Sangat penting bagi konstruksi untuk memiliki expander antara salinan vertex ("cloud" dari vertex). Jika tidak, Anda tidak akan dapat mendebat bahwa nilai penetapan musuh ke simpul lebih baik menugaskan simpul tersebut dengan nilai yang sama.

Secara khusus, jika alih-alih expander Anda memiliki siklus, prover dapat menetapkan satu setengah siklus satu nilai, dan setengah lainnya siklus lain nilai. Dengan cara ini dengan probabilitas yang baik, verifier tidak akan menangkap ketidakkonsistenan di antara simpul-simpul, tetapi Anda tidak dapat menggunakan tingkat kesehatan grafik asli untuk membuktikan tingkat kesehatan grafik baru (seperti membiarkan peribahasa dalam grafik asli menggunakan dua tugas yang berbeda untuk vertex).

Dana Moshkovitz
sumber
Jadi, argumennya justru gagal pada titik ini karena kita tidak dapat mengontrol parameter kesehatan atau celah (menggunakan parameter kesehatan untuk grafik asli)?
2
@Abhishek: mengontrol parameter kesehatan untuk grafik baru adalah bagaimana Anda mengontrol kesenjangan (= kesenjangan antara kelengkapan dan kesehatan, dan kelengkapan tidak berubah dalam grafik baru). Anggaplah seorang expander sebagai pendekatan kecil dari grafik lengkap: grafik lengkap akan memaksa Anda untuk menggunakan tugas yang sama untuk semua simpul.
Sasho Nikolov
2
@Abhishek: ya.
Dana Moshkovitz
@Abhishek jika jawaban ini adalah yang Anda cari (dan sepertinya memang demikian), Anda harus mengklik tanda centang di bawah skor jawaban untuk menerimanya.
Suresh Venkat