Bukti interaktif untuk tingkat hierarki polinomial

33

Kami tahu bahwa jika Anda memiliki mesin PSPACE, itu cukup kuat untuk memberikan bukti interaktif dari level apa pun hierarki polinomial. (Dan jika saya ingat benar, semua yang Anda butuhkan adalah #P.) Tetapi misalkan Anda ingin memberikan bukti keanggotaan interaktif dalam $\Sigma_2$ bahasa. Apakah cukup untuk menyelesaikan masalah di $\Sigma_2$ ? Apakah menyelesaikan masalah di $\Sigma_5$ memadai? Lebih umum, jika Anda dapat memecahkan masalah atau , untuk apa apakah ini cukup untuk menghasilkan bukti interaktif dari semua bahasa di ? $\Sigma_k$ $\Pi_k$ $\Sigma_\ell$ $\Sigma_\ell$

Pertanyaan ini diinspirasi oleh pertanyaan pertukaran stackstory ini .

cc.complexity-theory interactive-proofs Peter Shor
sumber

Apakah Anda hanya tertarik pada kasing tunggal atau Anda tertarik pada kasing ganda? Tampak bagi saya bahwa cara yang jelas untuk menyerang ini adalah melalui PCP, yang mungkin lurus ke depan untuk dua prover, tetapi mungkin tidak akan bekerja untuk prover tunggal.

Joe Fitzsimons

1

Saya akan tertarik pada kedua kasus. Saya telah bertanya-tanya tentang pertanyaan ini untuk prover tunggal untuk beberapa waktu, tetapi tidak memikirkan sama sekali tentang beberapa prover.

Peter Shor

4

@ Peter: Melihat dari atas IP = kertas PSPACE, tampaknya bahwa bukti akan pergi melalui menggunakan

(yang lengkap untuk

) daripada QBF, asalkan Anda memiliki prover cukup kuat untuk menghitung identitas polinomial yang timbul dari aritmitisasi

. Apakah saya melewatkan sesuatu?

{QBF}_{k}

$\mbox{QBF}_k$

Σ_{k}^{P}

$\Sigma^P_k$

{QBF}_{k}

$\mbox{QBF}_k$

Joe Fitzsimons

1

@ Jo, saya belum mempertimbangkan ide itu; mungkin berhasil.

Peter Shor

2

Joe, mungkin Anda harus mempostingnya sebagai jawaban

Suresh Venkat

25

Bahkan untuk memberikan IP untuk CoNP, menggunakan teknik saat ini, orang perlu menghitung, yaitu menggunakan penghitungan, yang pada dasarnya berarti kekuatan penuh #P. Pepatah yang lebih lemah bahkan untuk CoNP akan sangat menarik, saya pikir (khususnya akan menyiratkan teknik non relativing baru.)

Noam
sumber

@ Peter: Noam benar. Saya mengutip garis-garis berikut dari sini : ... mendasarkan hashing tabrakan pada kekerasan kasus terburuk NP melalui pengurangan kotak hitam menyiratkan sistem bukti interaktif untuk co-NP dengan prover dalam BPP ^ NP ... Semua diketahui (bahkan multi-prover) sistem bukti untuk co-NP memerlukan prover dengan kompleksitas #P ...

MS Dousti

Dalam hal ini jawaban saya kemungkinan besar adalah omong kosong. Terima kasih telah menunjukkan ini.

Joe Fitzsimons

Sebenarnya, ini benar-benar menarik, mengingat bahwa bukti interaktif untuk Graph non-Isomorphism hanya membutuhkan peribahasa dengan oracle untuk masalah itu. Rasanya seperti bukti bahwa GI baik sangat sangat lemah (seperti di P) atau batas untuk bukti interaktif tingkat hirarki polinom sangat mungkin longgar.

Joe Fitzsimons

1

Saya menganggap beberapa prover tidak dikenal membantu. Apakah ini benar?

Peter Shor

1

@ Jo Bukti untuk grafik non isomorfisme adalah bukti koin publik putaran konstan, sehingga menempatkannya di kelas AM (secara luas diyakini sama dengan NP, dan karenanya GI dan GNI diyakini dalam

). Ini jauh lebih rendah daripada bukti putaran polinomial yang diyakini diperlukan untuk membuktikan keanggotaan dalam masalah lengkap TNP.

N P \cap c o N P

$NP \cap coNP$

Boaz Barak

21

Ini adalah masalah terbuka (luar biasa) yang telah saya kerjakan dari waktu ke waktu tanpa hasil.

Avi Wigderson dan saya menyebutkan masalah dalam makalah algebrization kami , di mana kami mengangkat pertanyaan apakah penahanan seperti CONP ⊆ IP _NP dapat dibuktikan melalui teknik algebrizing. (Di sini IP _NP menunjukkan IP dengan verifier BPP dan prover BPP ^NP .) Jika (seperti yang saya duga) jawabannya adalah tidak, maka itu akan memberikan alasan formal mengapa setiap protokol interaktif seperti yang diminta Peter akan memerlukan non-relativizing teknik yang melampaui "secara fundamental" yang digunakan untuk IP = PSPACE.

Pertanyaan analog adalah apakah BQP = IP _BQP atau tidak , di mana IP _BQP berarti IP dengan verifier BPP dan prover BQP (quantum polynomial-time). Pertanyaan itu juga terbuka --- meskipun terobosan baru - baru ini oleh Broadbent, Fitzsimons, dan Kashefi menunjukkan bahwa pernyataan yang berkaitan erat itu benar.

Scott Aaronson
sumber

20

Ya, pertanyaan apakah coNP memiliki bukti interaktif di mana prover lebih lemah dari #P (katakanlah, polytime dengan akses ke NP oracle) adalah pertanyaan terbuka yang sudah dikenal luas. Makalah baru-baru ini dari Haitner, Mahmoody dan Xiao membahas pertanyaan ini dan menunjukkan beberapa konsekuensi dari asumsi bahwa ini tidak dapat dilakukan.

Boaz Barak
sumber

11

Karena Suresh telah menyarankan saya mengirim komentar saya sebagai jawaban, saya akan melakukannya. Namun, saya tidak menganggap ini sebagai jawaban penuh karena saya belum berusaha untuk membuktikan ini, dan itu mungkin menjadi jalan buntu.

$\mbox{QBF}_k$ $\Sigma^P_k$ $\mbox{QBF}_k$ $\Sigma^P_k$

Joe Fitzsimons
sumber

masalah sudah muncul dalam bukti untuk coNP. Protokol sumcheck memiliki n ronde (satu untuk setiap variabel). Dalam setiap putaran, pepatah perlu menghasilkan koefisien polinomial yang diperoleh dari sejumlah besar eksponensial. Saya tidak tahu bagaimana cara melakukannya menggunakan daya lebih kecil dari #P.

Boaz Barak

@ Boas: Ya, saya pikir pendekatan ini ditakdirkan untuk gagal. Saya pikir saya telah melihat versi arithmetization dilakukan di suatu tempat sedemikian rupa sehingga polinomial hanya mengambil nilai 1 atau 0 untuk input 0s dan 1s. Jika ini masalahnya, sepertinya Anda bisa menggunakan oracle untuk masalah keputusan yang sesuai. Kemudian lagi, saya mungkin hanya membayangkan itu!

Joe Fitzsimons

Bukti interaktif untuk tingkat hierarki polinomial

Jawaban: