Apakah memerlukan keunikan jawaban yang valid untuk Merlin membatasi kekuatan protokol Arthur-Merlin?

Pembukaan.

Kelas kompleksitas AM adalah masalah-masalah yang dapat diselesaikan dengan sistem bukti interaktif dua putaran antara prover "Merlin" dan verifier "Arthur". Masalah - yang menguji beberapa properti dari objek X - adalah pada AM jika:

• Untuk contoh YA , untuk pesan "tantangan" acak (panjang polinomial) yang dihasilkan Arthur, dengan probabilitas tinggi Merlin dapat merumuskan jawaban (panjang polinomial) yang dapat digunakan Arthur sebagai bukti bahwa X memiliki properti;

• Untuk NO contoh, untuk tantangan pesan acak Arthur menghasilkan, dengan probabilitas tinggi Merlin tidak bisa merumuskan jawaban yang dapat digunakan sebagai bukti untuk properti yang sedang diuji untuk di X .

- Kelas yang dijelaskan tidak berubah jika kita mengharuskan Merlin untuk memberikan jawaban yang bermanfaat tidak hanya dengan probabilitas tinggi, tetapi untuk setiap tantangan yang mungkin dikeluarkan Arthur; kita dapat mengatakan dalam kasus ini bahwa kita membutuhkan jawaban Merlin selalu valid untuk contoh YA , dan apa yang tes Arthur adalah validitas dari jawabannya. Jadi, jika Merlin pernah menghasilkan respons yang tidak valid, Arthur tahu bahwa instance masalah adalah instance NO . Ini adalah pengaturan yang saya ingin pertimbangkan.

Contohnya adalah Graph Non-Isomorphism: diberikan grafik G dan H dengan set label vertex yang sama, Arthur dapat secara acak memilih salah satu grafik dan menghasilkan versi "scramble" F dengan membubuhkan label vertex-nya, mengirimkan presentasi ke Merlin . Jika kedua grafik tersebut non-isomorfik, Merlin dapat mengidentifikasi G atau H Arthur mana yang dipilih dengan menentukan apakah F  ≅  G atau F  ≅  H , dan dapat merespons dengan mengidentifikasi mana dari kedua F yang isomorfik. Namun, jika dua grafik G dan H isomorfis, Merlin tidak dapat membedakan grafik manaF berasal, dan jawaban apa pun yang dia berikan hanya bisa benar secara kebetulan. Jadi, untuk contoh YA, Merlin selalu dapat mengirim respons yang valid untuk setiap tantangan; untuk NO instance tanggapan apa pun yang mungkin dikirim Merlin akan dengan probabilitas tinggi tidak valid.

Dalam masalah di atas, tidak hanya ada tanggapan yang valid yang dapat diberikan Merlin kepada Arthur untuk setiap tantangan, tetapi pada kenyataannya ada respons yang unik dan valid: yaitu,  menunjukkan G atau H Arthur yang dipilih, mengingat hal ini dapat ditentukan oleh mengidentifikasi yang isomorfik ke F .

Pertanyaan.

Apakah memaksakan batasan di sepanjang garis ini - bahwa untuk contoh YA , untuk setiap tantangan yang mungkin dikirim Arthur, tepat ada satu respons yang valid untuk Merlin - menghasilkan kelas yang lebih ketat, dalam arti menghasilkan kelas yang tidak diketahui setara dengan AM ?

Kertas Koiran ini Hilbert Nullstellensatz adalah di Polinomial Hierarchy menyediakan public-koin protokol Arthur-Merlin untuk menetapkan bahwa suatu sistem $m$ persamaan pada $n$ tidak diketahui memiliki solusi di $\mathbb{C}^n$ , bergantung pada Generalized Riemann Hipotesis. Di sini Merlin menemukan $p$ utama dengan $H(p)=0$ untuk beberapa hash acak $H$ , bersama dengan solusi $(a_0,a_1,\cdots, a_n)$ untuk masing-masing $m$ persamaan$\bmod p$.

Jika sistem persamaan tidak memiliki solusi $\bmod p$ , maka hanya akan ada sejumlah terbatas modulo $p$ yang ada solusi. Jika sistem memang memiliki solusi $\bmod p$ , maka tanpa syarat akan ada kepadatan positif $p$ dengan solusi, dan GRH memungkinkan bahwa $p$ dengan solusi "merata" dalam beberapa hal, sehingga Merlin mendapat kemenangan.

Meskipun Koiran memberi contoh sistem dipecahkan di mana kepadatan $p$ adalah eksponensial kecil, Koiran menunjukkan bahwa jika sistem dipecahkan di $\mathbb{C}^n$ , maka dalam kebanyakan kasus akan ada sejumlah besar dari $p$ (dan sejumlah besar $a$ ) ; memang sekitar $1-1/e$ primes harus memiliki solusi IIRCC.

Dengan demikian, dalam masalah di atas, tidak hanya ada tanggapan yang valid yang dapat diberikan Merlin kepada Arthur untuk setiap tantangan, tetapi pada kenyataannya mungkin ada masalah besar. tanggapan yang valid.

$p$$p$