Beigi, Shor dan Watrous memiliki sangat bagus kertas pada kekuatan bukti interaktif kuantum dengan pesan singkat. Mereka mempertimbangkan tiga varian 'pesan singkat', dan yang spesifik yang saya pedulikan adalah varian kedua di mana sejumlah pesan dapat dikirim, tetapi total panjang pesan harus logaritmik. Secara khusus mereka menunjukkan bahwa sistem bukti interaktif tersebut memiliki kekuatan ekspresif BQP.
Yang ingin saya ketahui adalah apakah ada hasil analog untuk pengaturan multi-prover, baik untuk verifier klasik atau kuantum. Apakah ada hasil kompleksitas non-sepele yang dikenal untuk bukti interaktif multi-prover di mana total panjang semua pesan dibatasi untuk menjadi logaritmik dalam ukuran masalah?
cc.complexity-theory
quantum-computing
interactive-proofs
Joe Fitzsimons
sumber
sumber
Jawaban:
Kasus klasik lengkap (MIP)
Jika verifikasinya klasik dan tidak ada keterikatan sebelumnya di antara prover, kelas Anda berisi BPP∪NP dan terkandung dalam MA .
Itu sepele bahwa BPP adalah batas bawah. Untuk menunjukkan bahwa kelas tersebut mengandung NP, pertimbangkan sistem bukti interaktif interaktif satu putaran dua-prover untuk 3-warna dengan kelengkapan sempurna dan kesalahan kesehatan 1 /1 / poli. Jika Anda ingin mengurangi kesalahan tingkat ke konstanta, gabungkan ini dengan teorema PCP.
Adapun batas atas, pernyataan kuat berikut ini berlaku: MIP dengan batasan bahwa panjang pesan total dari verifier untuk setiap prover adalah O (log n ) sama dengan MA. Ini karena strategi masing-masing pepatah dapat dijelaskan dengan serangkaian panjang polinomial.
Menariknya, batas atas lainnya ada ketika sistem memiliki kelengkapan yang sempurna. Yaitu, sistem bukti interaktif multi-prover dengan kelengkapan sempurna dengan komunikasi total O (log n ) -bit mengenali paling banyak P NP [log] , dan ini berlaku bahkan jika kita mengizinkan kesalahan tingkat kelancaran kesehatan. Untuk membuktikan ini dalam kasus dua provers, biarkan x s menjadi gabungan dari semua jawaban yang diberikan oleh prover pertama ketika gabungan dari semua pertanyaan dengan prover pertama adalah s , dan mendefinisikan y t analog untuk prover kedua. Untuk diterima oleh verifier dengan pasti, variabel-variabel ini x s dan y tharus memenuhi batasan tertentu, dan perhatikan bahwa ini adalah 2CSP. Paling banyak ada poli ( n ) pilihan untuk tupel ( s , t , x s , y t ), dan untuk setiap pilihan, kita dapat menggunakan oracle NP untuk menguji apakah verifier menolak tupel itu. Oleh karena itu, dengan oracle NP, kita bisa daftar semua kendala pada variabel x s dan y tdalam waktu polinomial. Akhirnya, kami menggunakan NP oracle sekali lagi untuk menguji apakah ada tugas untuk variabel-variabel ini yang memenuhi semua kendala. Meskipun algoritma ini menggunakan oracle NP secara polinomial berkali-kali, semua permintaan kecuali yang terakhir dapat dibuat secara paralel, dan oleh karena itu ini dapat dikonversi ke algoritma [log] P NP . Kasing lebih dari dua prover analog.
Batas atas ini menyiratkan bahwa meskipun setiap sistem MA dapat diubah menjadi satu dengan kelengkapan sempurna, kami tidak dapat berharap untuk sistem bukti interaktif multi-prover dengan kelengkapan sempurna dengan komunikasi O (log n ) -bit kecuali jika MA⊆P NP [log] . Saya tidak tahu seberapa kecil inklusi MA⊆P NP [log] , tetapi saya hanya mencatat bahwa Zoologi Kompleksitas menyatakan bahwa ada oracle relatif terhadap NP BPP⊈ P (dan karenanya jelas MA⊈P NP [log] ).
(Dalam kasus prover tunggal, Teorema 2 dari Goldreich dan Håstad [GH98] menyiratkan bahwa IP dengan panjang pesan total O (log n ) bit sama dengan BPP.)
Ditambahkan . Karakterisasi yang diperlukan dan cukup adalah sebagai berikut.
Untuk menjelaskan karakterisasi ini, kita memerlukan varian gagasan reduksibilitas Karp (reduksibilitas polinomial banyak waktu satu). Untuk dua masalah keputusan A dan B , katakanlah A adalah FP BPP -dapat diturunkan ke B (saya tahu, ini adalah nama yang mengerikan) ketika ada mesin Turing polinomial-deterministik M dengan akses ke oracle BPP yang memetakan ya- contoh untuk yes-instance dan no-instances ke no-instance, di mana kami mengizinkan akses oracle "non-pintar" (yang berarti bahwa Mdapat mengajukan pertanyaan kepada oracle BPP tentang contoh yang tidak memenuhi janji masalah BPP, dalam hal ini oracle mengembalikan ya atau tidak secara sewenang-wenang). Maka dapat dibuktikan bahwa kondisi berikut pada masalah A adalah setara.
(i) A memiliki sistem bukti interaktif multi-prover dengan komunikasi O (log n ) -bit dan kesalahan dua sisi.
(ii) A memiliki sistem bukti interaktif satu putaran dua putaran dengan komunikasi O (log n ), kesalahan kelengkapan kecil secara eksponensial, dan kesalahan kesehatan konstan.
(iii) A adalah FP- BPP yang dapat direduksi menjadi masalah dalam NP.
(Gagasan bukti: Implikasi (ii) ⇒ (i) adalah sepele. Implikasi (i) ⇒ (iii) dapat diperoleh dengan cara yang mirip dengan bukti di atas dalam kasus kesalahan satu sisi. Implikasi (iii) ⇒ (ii) ) mengikuti dari teorema PCP karena kelas dari kondisi kondisi memuaskan (ii) ditutup berdasarkan FP BPP -reducibility.)
Verifikasi klasik dengan prover terjerat (MIP *)
Selanjutnya pertimbangkan kasus dengan verifier klasik dan prover terjerat. Dalam hal ini, kelas dengan kesalahan terikat lagi berisi BPP∪NP.
Kempe, Kobayashi, Matsumoto, Toner, dan Vidick [KKMTV11] menunjukkan bahwa setiap masalah di NP memiliki sistem bukti interaktif satu putaran tiga-pepatah dengan kelengkapan sempurna dan kesalahan kesehatan 1−1 / poly di mana total panjang pesan adalah O ( log n ) bit, dan tingkat kesehatan berlaku melawan prover terjerat. Oleh karena itu, MIP * dengan panjang pesan total O (log n ) bit dan kesalahan terikat berisi NP. Hasil selanjutnya oleh Ito, Kobayashi, dan Matsumoto [IKM09] (plug shameless) mengurangi jumlah prover dari tiga menjadi dua. Kasus kesehatan konstan terbuka di bagian atas pengetahuan saya.
Tidak diketahui apakah MIP * dengan panjang pesan total O (log n ) bit terkandung dalam kelas R dari masalah yang dapat ditentukan atau tidak, dan pertanyaan ini setara dengan apakah MIP * ⊆R (masalah terbuka lainnya) oleh argumen padding.
Referensi
[GH98] Oded Goldreich dan Johan Håstad. Pada kompleksitas bukti interaktif dengan komunikasi terbatas. Information Processing Letters , 67 (4): 205–214, Agustus 1998. http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1
[IKM09] Tsuyoshi Ito, Hirotada Kobayashi, dan Keiji Matsumoto. Oracularisasi dan bukti interaktif satu putaran dua-prover terhadap strategi non-lokal. Prosiding: Konferensi IEEE Tahunan Kedua Puluh Empat tentang Kompleksitas Komputasi (CCC 2009) , 217–228, Juli 2009. http://dx.doi.org/10.1109/CCC.2009.22
[KKMTV11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, dan Thomas Vidick. Game terjerat sulit diperkirakan. Jurnal SIAM tentang Komputer , 40 (3): 848–877, 2011. http://dx.doi.org/10.1137/090751293
sumber