Lansekap sistem bukti interaktif

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 .

cc.complexity-theory big-picture interactive-proofs Vijay D
sumber

Apa yang sudah kamu ketahui?

Tsuyoshi Ito

Ada lebih dari 1 parameter variabel dalam sistem bukti interaktif: Apa kekuatan verifier, apa kekuatan prover, apa jenis (dan jumlah) komunikasi yang diizinkan, apakah mereka memiliki keacakan yang dibagikan sebelumnya, apakah verifier harus membaca seluruh pesan dari pepatah atau apakah dia memiliki akses acak ke pesan, dll.

Robin Kothari

Setelah berpikir sedikit lagi, saya tidak berpikir bahwa saya dapat menjawab pertanyaan Anda secara memadai karena sistem bukti interaktif adalah topik yang luas dalam teori kompleksitas komputasi. Anda mungkin ingin memeriksa Bab 9 Kompleksitas Komputasi: Perspektif Konseptual oleh Goldreich atau Bab 8 dan 11 Kompleksitas Komputasi: Suatu Pendekatan Modern oleh Arora dan Barak.

Tsuyoshi Ito

@ VijayD: Ya, itu bagian dari masalah. Dalam penokohan kompleksitas deskriptif, ada satu variabel (logika), sehingga saat Anda naik dari FO ke SO, Anda beralih dari AC0 ke PH, dll. Dalam sistem bukti interaktif, ada begitu banyak variabel sehingga tidak jelas bahwa lanskap bisa ditarik.

Robin Kothari

Saya tidak yakin pertanyaan ini cukup jelas. Ada jawaban yang sepele: setiap kelas dapat "ditandai" sebagai "bukti interaktif" di mana pepatah pada dasarnya tidak berbuat banyak dan pemverifikasi cukup kuat. Hal yang menarik tentang hasil IP = PSPACE dan MIP = NEXP (dan PCP [O (\ log n), O (1)] = NP) adalah verifikasinya sangat lemah.

Sasho Nikolov

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. $\mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)}$
, di mana pfa (verifier) adalah otomat terbatas hingga probabilistik satu arah yang berinteraksi dengan dua prover. $\mathsf{R} = \mathsf{2IP(pfa)}$
. $\mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)}$
. $\mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)}$
. $\mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)}$
, , dan lain-lain $\mathsf{P} = \mathsf{AM(log\mbox{-}space)}$ $\mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)}$

Beberapa hasil terbaru (sebagian besar kuantum):

$\mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)}$
$\mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)}$
$\mathsf{EXP}$
$\mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)}$
$\mathsf{NP}$
$\mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)}$

Abuzer Yakaryilmaz
sumber

Terima kasih! Inilah yang saya inginkan. Saya bingung bagaimana memperbaiki pertanyaan saya, yang terlalu samar untuk para ahli, dan senang Anda mengerti maksud saya.

Vijay D

Kalau begitu, mengapa Anda tidak menandainya sebagai jawaban terbaik?

Cem Say

Karena siapa yang tahu apa yang akan terjadi besok? Saya ingin seminggu atau 10 hari setelah memposting untuk memutuskan.

Vijay D

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.

Atau Meir
sumber