Komputasi Acak dan Interaktif

Memungkinkan algoritma untuk melempar koin atau terlibat dalam dialog dengan pembukti yang kuat tetapi tidak tepercaya menghasilkan kelas kompleksitas seperti BPP dan IP yang membentuk kembali pemahaman kita tentang apa yang dapat dicapai oleh verifikasi yang efisien.

Definition

Komputasi acak melengkapi mesin dengan akses ke bit acak dan mengukur probabilitas jawaban yang benar, sementara komputasi interaktif memungkinkan verifikator waktu polinomial bertukar pesan dengan pembukti; kelas yang dihasilkan menangkap masalah yang dapat dipecahkan dengan kesalahan terbatas atau dapat diverifikasi melalui interaksi.

Scope

Topik ini mencakup kelas kompleksitas probabilistik termasuk BPP, RP, dan ZPP serta pertanyaan apakah keacakan dapat dihilangkan, sistem bukti interaktif dan teorema yang mengidentifikasi IP dengan PSPACE, bukti tanpa pengetahuan (zero-knowledge proofs), dan bukti yang dapat diperiksa secara probabilistik (probabilistically checkable proofs) yang mendasari kekerasan aproksimasi.

Core questions

• Apakah akses ke keacakan memungkinkan algoritma memecahkan lebih banyak masalah secara efisien?
• Dapatkah verifikator terbatas memeriksa klaim yang dibuat oleh pembukti yang tidak tepercaya dan kuat?
• Bagaimana seseorang dapat diyakinkan bahwa suatu pernyataan itu benar tanpa mempelajari hal lain?
• Bagaimana pemeriksaan bukti interaktif dan probabilistik membatasi aproksimasi?

Key theories

IP sama dengan PSPACE

Bahasa-bahasa yang dapat dibuktikan oleh protokol interaktif antara verifikator waktu polinomial dan pembukti yang mahakuasa adalah persis yang dapat diputuskan dalam ruang polinomial, sebuah ukuran yang mencolok dari kekuatan interaksi.

Teorema PCP

Setiap masalah dalam NP memiliki bukti yang dapat diverifikasi dengan hanya membaca sejumlah konstan bit yang dipilih secara acak, sebuah hasil yang menentukan ambang batas yang tepat di mana mengaproksimasi banyak masalah optimasi adalah NP-hard.

Clinical relevance

Gagasan-gagasan ini memiliki dampak teknologi langsung: bukti tanpa pengetahuan memungkinkan otentikasi dan protokol yang menjaga privasi serta mendukung komputasi yang dapat diverifikasi dalam blockchain, sementara bukti yang dapat diperiksa secara probabilistik menjelaskan mengapa banyak masalah optimasi tidak dapat diaproksimasi secara efisien, membimbing di mana algoritma aproksimasi dapat dan tidak dapat berhasil.

History

Bukti interaktif dan tanpa pengetahuan diperkenalkan oleh Goldwasser, Micali, dan Rackoff serta oleh Babai pada pertengahan 1980-an. Shamir membuktikan IP sama dengan PSPACE pada tahun 1990, dan teorema PCP, yang diselesaikan oleh Arora dan lainnya pada awal 1990-an, merevolusi studi aproksimasi, sementara dugaan yang masih berlaku bahwa waktu polinomial acak sama dengan waktu polinomial deterministik masih belum terpecahkan.

Debates

Apakah keacakan menambah kekuatan komputasi yang asli?

Banyak hasil menunjukkan BPP sama dengan P di bawah asumsi kekerasan yang masuk akal, yang berarti keacakan pada prinsipnya dapat dihilangkan dari algoritma yang efisien. Apakah derandomisasi ini berlaku tanpa syarat masih belum terpecahkan, menyisakan pertanyaan seberapa esensial keacakan itu.

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

Bagaimana melempar koin dapat membantu algoritma?

Keacakan memungkinkan algoritma menghindari masukan kasus terburuk dengan membuat pilihan yang tidak dapat diprediksi oleh lawan, seringkali menghasilkan prosedur yang lebih sederhana atau lebih cepat, seperti dalam pengujian primalitas. Kelas kesalahan terbatas BPP menangkap masalah yang dapat dipecahkan dengan cara ini dengan peluang kesalahan yang kecil dan dapat dikendalikan.

Apa itu bukti tanpa pengetahuan?

Ini adalah protokol interaktif yang meyakinkan verifikator bahwa suatu pernyataan itu benar tanpa mengungkapkan apa pun selain kebenarannya, bahkan mengapa itu berlaku. Bukti semacam itu memungkinkan, misalnya, membuktikan Anda tahu kata sandi atau rahasia tanpa mengungkapkannya, dan itu adalah dasar bagi privasi kriptografi modern.