Bukti Interaktif untuk CoNP

9

Saya mencoba memahami sistem bukti interaktif dan mencoba masalah berikut sebagai latihan. Kita tahu bahwa dan , jadi datang dengan sistem bukti interaktif (mudah dimengerti) untuk ? $PH \subseteq PSPACE$ $IP=PSPACE$ $PH$

Sistem bukti interaktif untuk adalah sepele, tetapi saya gagal mendapatkan sistem bukti interaktif bahkan untuk . Apakah Anda tahu sistem bukti interaktif interaktif (maksud saya secara eksplisit tanpa melalui rute ) untuk ? $NP$ $coNP$ $IP=PSPACE$ $coNP$

complexity-theory interactive-proof-systems Shitikanth
sumber

Bisakah Anda mengklarifikasi apa yang Anda maksud dengan sistem bukti interaktif? Bagi mereka yang tidak terbiasa dengan istilah ini.

jmite

3

Bahkan inklusi memerlukan teknik nonrelativizing; satu-satunya cara yang diketahui untuk menunjukkannya adalah melalui algebrization, seperti dalam jawaban Yuval. Menampilkan hanyalah sedikit modifikasi teknis dari bukti ini.

c o N P \subseteq I P

$coNP \subseteq IP$

I P = P S P A C E

$IP=PSPACE$

sdcvvc

2

@ sdcvvc, saya pikir komentar Anda layak diposting sebagai jawaban. Ini menjelaskan mengapa tidak ada contoh sesederhana yang untuk NP.

Kaveh

6

Wikipedia menguraikan contoh seperti itu. Pertimbangkan masalah UNNAS lengkap coNP: diberi CNF pada variabel , kami ingin meyakinkan verifier bahwa tidak memuaskan. Kami ke polinomial dan memilih beberapa . Biarkan Protokol hasil sebagai berikut: $\varphi$ $n$ $\varphi$ $\varphi$ $p$ $q$

p (x_{1}, \dots, x_{k}) = \sum_{x_{k + 1} = 0}^{1} \dots \sum_{x_{n} = 0}^{1} p (x_{1}, \dots, x_{n}) .

$p(x_1,\ldots,x_k) = \sum_{x_{k+1}=0}^1 \cdots \sum_{x_n=0}^1 p(x_1,\ldots,x_n).$

Prover mengirimkan verifier sebagai prime , dan yang terakhir memverifikasi bahwa adalah prime. $q \in (2^n,2^{n+1})$ $q$
Prover mengirimkan verifier . Verifier memverifikasi bahwa , dan mengirimkan prover secara acak . $p(z) \in \mathbb{Z}_q[z]$ $p(0) + p(1) = 0$ $r_1$
Prover mengirimkan verifier . Verifier memverifikasi bahwa , dan mengirimkan prover secara acak . $p(r_1,z) \in \mathbb{Z}_q[z]$ $p(r_1,0) + p(r_1,1) = p(r_1)$ $r_2$
Akhirnya, verifikasi mendapatkan , dan memverifikasi bahwa ia memiliki nilai yang benar dengan mengevaluasi secara langsung. $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$ $p$

Karena derajat kecil dibandingkan dengan , jika pepatah curang maka pemverifikasi kemungkinan akan menangkapnya (lihat Wikipedia untuk buktinya, atau kerjakan sendiri menggunakan lemma Schwartz-Zippel). $p$ $q$

Yuval Filmus
sumber

-1

Grafik non-isomorfisme pada Bukti yang Tidak Menghasilkan Apa-apa Tetapi Keabsahannya atau Semua Bahasa di NP memiliki Bukti Tanpa Pengetahuan , Goldreich, Micali dan Wigderson, JACM, 1991.

Input umum adalah sepasang grafik: . Pada awal setiap putaran, pihak yang memverifikasi memilih indeks secara acak dan mengirimkan permutasi acak grafik . Pihak terbukti merespons dengan indeks . $G_1, G_2$ $i \in \{1,2\}$ $G_i$ $b \in \{1,2\}$

Properti kelengkapan: untuk grafik non-isomorfik, pepatah selalu memberikan respons yang benar . $b=i$

Tingkat kesehatan: untuk grafik isomorfik, prover memberikan respons yang benar dengan probabilitas . $\frac{1}{2}$

Vadym Fedyukovych
sumber

Tolong beri referensi yang tepat untuk artikel peer-review dan ringkasan singkat dari konten. Tautan seperti yang Anda berikan cenderung rusak, dan kemudian jawaban Anda tidak berisi informasi.

Raphael

Bukti Interaktif untuk CoNP

Jawaban: