Kesetaraan Dua Definisi Kelengkapan & Kesehatan dalam Sistem Bukti Interaktif

11

Kelengkapan dan kesehatan dalam sistem bukti interaktif secara informal didefinisikan sebagai:

  • Kelengkapan: Jika pernyataan itu benar, maka orang yang jujur dapat meyakinkan orang yang jujur akan kebenaran fakta ini .

  • Keakuratan: Jika suatu pernyataan salah, pemalsu selingkuh tidak dapat meyakinkan verifier jujur (validitas pernyataan palsu) whp

Istilah "whp" dapat ditafsirkan sebagai "dengan probabilitas lebih besar dari (katakanlah) 2/3," atau "dengan probabilitas lebih besar dari kebalikan dari polinomial apa pun." Tampaknya tidak penting untuk diskusi berikut sebagai interpretasi "whp" apa yang harus dipilih.

Bagian yang rumit adalah bagaimana probabilitas dihitung: Dalam beberapa sumber, probabilitas tersebut diambil alih koin acak baik dari prover maupun verifier. Di sumber lain, probabilitasnya hanya dihitung dari koin acak pemeriksa. Yang terakhir ini biasanya dibenarkan sebagai: "apa pun koin acak dari pepatah, pemverifikasi membuat keputusan yang tepat."

Bagi saya, kedua definisi probabilitas tersebut tampak setara; namun saya tidak dapat membuktikan ini. Apakah saya benar? Bisakah Anda membuktikannya setara?

cc.complexity-theory interactive-proofs Luar biasa
sumber
2
Anda juga harus mempertimbangkan apakah Anda merujuk pada koin "publik" atau koin "pribadi". Dalam pengaturan koin publik baik pepatah dan pemverifikasi tahu hasil dari pilihan acak, dan untuk koin pribadi, pepatah tidak tahu pilihan acak pemverifikasi. Dalam kasus yang terakhir ini, Anda hanya peduli tentang apa yang dilakukan verifier tanpa melihat prover karena prover tidak tahu lemparan koin acak.
Marcos Villagra
@Marcos: Lihatlah definisi asli dari bukti interaktif, yang merupakan koin "pribadi". Kalimat terakhir kolom pertama pada halaman 293, yang digarisbawahi, menyatakan bahwa "probabilitas hanya diambil atas lemparan koin B sendiri." (Di sini, B adalah verifikator.) Di sisi lain, versi jurnal dari makalah yang disebutkan di atas memungkinkan probabilitas untuk diambil alih dengan lemparan koin kedua belah pihak. Ini mungkin sumber kebingungan, bukan?
MS Dousti
@ Sadq: Begitu, saya tidak tahu tentang perbedaan antara jurnal dan versi konferensi. Namun, untuk koin pribadi, saya tidak mengerti gunanya memperhitungkan pelemparan koin yang tepat, karena dia bisa memutuskan untuk tidak memberi tahu verifier tentangnya. Verifier adalah penanggung jawab untuk memutuskan penerimaan atau penolakan, dan dia mungkin tidak tahu apa yang dilakukan pepatah.
Marcos Villagra
1
@Marcos: Anda benar, tetapi alasan yang sama berlaku untuk bukti koin publik; karena dalam sistem itu lemparan koin yang tepat masih bersifat pribadi (hanya koin verifikator yang bersifat publik). Secara umum, seseorang dapat mempertimbangkan prover deterministik: Karena prover sangat kuat, ia tidak perlu keacakan dan dapat memilih jawaban optimal secara deterministik. Namun jenis penalaran ini tidak berfungsi jika kita mempertimbangkan sistem tanpa pengetahuan, di mana strategi pepatah harus probabilistik (jika tidak, pengetahuannya akan bocor).
MS Dousti
2
(Lanjutan) Jika pepatah diacak, maka saya pikir formulasi yang tepat adalah untuk menghitung probabilitas dari kedua lemparan koin dari pepatah dan pemverifikasi: Sementara seperti kata Marcos, pemverifikasi bertanggung jawab atas keputusan akhir, keputusannya adalah dibuat (antara lain) berdasarkan pesan yang berasal dari pepatah. Mengingat fakta bahwa pepatah itu diacak, lemparan koinnya tentu saja memengaruhi pesan yang ia kirim. Oleh karena itu, lemparan koin pepatah memengaruhi kemungkinan penerimaan. Apakah saya benar?
MS Dousti

Jawaban:

6

Provernya "sangat kuat dan memiliki sumber daya komputasi yang tidak terbatas" sehingga tidak membutuhkan bit acak. Dengan demikian satu-satunya keacakan adalah keacakan dari pemeriksa.

Jika prover menggunakan bit acak, ia harus menggantinya dengan string bit acak yang paling mungkin membuat verifier menerima (ini berlaku untuk prover jujur ​​dan tidak jujur). Selanjutnya, prover dapat menentukan bit string optimal ini karena provernya "serba kuat".

Tyson Williams
sumber
1
Seperti yang saya katakan dalam komentar di atas, ini hanya benar ketika Anda mempertimbangkan bukti interaktif saja. Namun, hal-hal sangat berbeda jika Anda mempertimbangkan properti lain, seperti "nol pengetahuan" yang secara alami terhubung ke bukti interaktif.
MS Dousti
1
Cont'd: Secara khusus, Oren membuktikan yang berikut: "... di bawah definisi input tambahan pengetahuan nol, keacakan dari pepatah sangat penting untuk non-triviality dari sistem bukti nol pengetahuan. Dengan kata lain, bahasa apa pun yang memiliki sistem bukti nol pengetahuan tambahan input-input di mana prover yang menentukan untuk BPP. " (Lihat bagian 4.5 dari Oren untuk info lebih lanjut.) Oleh karena itu, Anda tidak selalu dapat berasumsi bahwa P adalah deterministik.
MS Dousti