Telah diketahui bahwa kumpulan bahasa yang memiliki sistem bukti interaktif dua-verver, di mana verifier berjalan dalam polinomial-time (MIP), adalah NEXP. Tetapi adakah batas yang diketahui tentang kekuatan bukti interaktif seperti itu ketika kaum proversi dibatasi kekuasaannya? Misalnya, apa kelas bahasa yang menerima bukti interaktif duaverver dengan prover waktu polinomial?
Lebih tepatnya, katakanlah pada input x saya izinkan prover untuk waktu pra-komputasi yang sewenang-wenang, tetapi begitu interaksi dengan verifier dimulai mereka dibatasi untuk menggunakan ruang polinom (termasuk menyimpan hasil dari setiap pra-komputasi), dan waktu polinomial untuk menghitung jawaban mereka terhadap pertanyaan pemeriksa. Mari kita juga berasumsi bahwa batas ruang dan waktu ini adalah polinom tetap dalam panjang pertanyaan yang akan dikirim oleh verifier (bukan panjang x), untuk mencegah solusi yang lebih sepele di mana verifier entah bagaimana akan menghabiskan ruang pepatah terikat dengan mengajukan lebih banyak pertanyaan secara polinomi.
Jelas, ini cukup untuk NP. Bagaimana dengan PSPACE? Jika hanya ada ruang yang terikat mereka bisa melakukannya, tetapi bagaimana dengan waktu yang terikat? Apakah ada hasil yang menarik ke arah itu?
Saya juga tertarik pada batasan lain yang dapat dipertimbangkan oleh orang-orang prover. Salah satunya adalah jumlah verifikasi komunikasi, yang saya pikir telah dipelajari secara menyeluruh dalam konteks PCP. Apa kendala menarik lainnya?
Jika kedua provers dibatasi menjadi dua mesin BQP yang tidak berkomunikasi satu sama lain, tetapi berbagi keterikatan, sementara verifier berada di BPP, maka kedua prover dapat membuktikan bahasa apa pun dalam BQP ke verifier klasik menggunakan Universal Blind Quantum Computation. protokol Broadbent, Fitzsimons, dan Kashefi. Protokol ini juga telah digunakan oleh penulis yang sama sebagai blok penyusun untuk menunjukkan QMIP = MIP * .
sumber