Pertanyaan pertama saya adalah apakah karakterisasi sistem bukti interaktif dikenal untuk semua kelas kompleksitas klasik. Saya akan memanggil P, NP, PSPACE, EXP, NEXP, EXPSPACE, fungsi rekursif dan berulang secara berulang klasik (antara lain). Secara khusus, apakah karakterisasi sistem bukti interaktif dikenal untuk fungsi berulang dan berulang secara berulang?
Saya hanya tahu bahwa IP = PSPACE dan MIP = NEXPTIME. Dengan `know 'berarti saya memahami definisi objek di kedua sisi kesetaraan dan mungkin memahami kesetaraan.
Pertanyaan kedua saya adalah apakah ada ringkasan grafis dari berbagai jenis sistem bukti interaktif dan kelas kompleksitas yang mereka cirikan.
Secara khusus, saya ingin referensi ke sosok yang mirip dengan gambar Immerman tentang karakterisasi kompleksitas deskripsi .
Jawaban:
Anda dapat menemukan banyak penokohan (khususnya pada verifier yang dibatasi ruang) dalam survei terkenal Condon: Kompleksitas sistem bukti interaktif yang dibatasi ruang .
Berikut adalah daftar beberapa di antaranya:
, di mana 2pfa (verifier) adalah otomat terbatas hingga probabilitas dua arah.RE=weak-IP(2pfa)
, di mana pfa (verifier) adalah otomat terbatas hingga probabilistik satu arah yang berinteraksi dengan dua prover.R=2IP(pfa)
.NEXP=2IP(pfa,poly-time)
.PSPACE=IP(log-space,poly-time)
.NP=oneway-IP(log-space,poly-time)=oneway-IP(log-space,log-random-bits)
, E X P = A M ( p o l y - s p a c e ) , dan lain-lainP=AM(log-space) EXP=AM(poly-space)
Beberapa hasil terbaru (sebagian besar kuantum):
sumber
NP sering dicirikan sebagai sistem bukti di mana pepatah mengirimkan bukti panjang polinom ke penentu waktu polinomial deterministik, dan setelah itu tidak ada interaksi. Kelas bahasa enumerable rekursif dapat dikarakterisasi dengan cara yang sama dengan mengganti "polinom" dengan "terbatas".
Selain itu, karena kelas bahasa rekursif R adalah persimpangan RE dan coRE, Anda dapat mengkarakterisasi R sebagai sistem bukti di mana pepatah perkasa dapat meyakinkan verifier waktu terbatas baik dalam validitas klaim yang benar maupun dalam ketidakabsahan klaim palsu.
Kelas EXP memiliki karakterisasi dalam hal sistem bukti dengan "prover yang bersaing" - yaitu, sistem bukti di mana terdapat prover yang mencoba meyakinkan verifier bahwa klaim itu benar dan sebuah refuter yang mencoba meyakinkan verifier bahwa klaim itu salah. Lihat kertas "Membuat game pendek" dari Feige dan Kilian untuk detail lebih lanjut.
sumber