Apakah PCP yang baik untuk NP memberi kami PCP yang baik untuk seluruh hierarki polinomial?

Teorema PCP menyatakan bahwa setiap masalah keputusan dalam NP memiliki bukti probabilistically checkable (atau setara, bahwa ada sistem bukti yang lengkap dan quasi-sound untuk teorema di NP menggunakan kompleksitas kueri konstan dan bit acak secara logaritmik).

"Kebijaksanaan rakyat" yang mengelilingi Teorema PCP (mengabaikan sejenak arti penting PCP terhadap teori aproksimasi) adalah bahwa ini berarti bukti yang ditulis dalam bahasa matematika yang ketat dapat diperiksa secara efisien hingga tingkat akurasi yang diinginkan tanpa perlu membaca keseluruhan bukti (atau banyak bukti sama sekali).

Saya tidak bisa melihat ini. Pertimbangkan ekstensi orde kedua ke logika proposisional dengan penggunaan quantifiers yang tidak dibatasi (yang saya katakan sudah lebih lemah dari ZFC, tetapi saya bukan ahli logika). Kita sudah dapat mulai untuk mengekspresikan teorema yang tidak dapat diakses oleh NP dengan bilangan kuantitatif.

Pertanyaan saya adalah apakah ada cara yang sederhana dan diketahui untuk 'membuka gulungan' dalam pernyataan proposisional tingkat tinggi sehingga PCP untuk teorema dalam NP berlaku sama baiknya untuk semua level PH. Bisa jadi ini tidak dapat dilakukan - bahwa membuka gulungan biaya, dalam kasus terburuk, beberapa bagian konstan dari kesehatan atau kebenaran sistem bukti kami.

lo.logic pcp polynomial-hierarchy Ross Snider
sumber

Sepertinya saya bahwa PCP untuk masalah yang hampir secara definisi menempatkan masalah dalam BPP, yang berarti bahwa ia ada dalam

oleh Sipser – Gács – Lautemann. Tapi mungkin juga lihat pertanyaan terkait ini .

Σ_{2} \cap Π_{2}

$\Sigma_2 \cap \Pi_2$

Peter Shor

Ini terdengar masuk akal, tapi saya bingung. Jika ini benar, bukankah akan memasukkan NP ke BPP?

Ross Snider

Ups. Saya seharusnya mengatakan MA, yang juga terkandung dalam .

Σ_{2} \cap Π_{2}

$\Sigma_2 \cap \Pi_2$

Peter Shor

ini tidak akan berhasil. PH resisten terhadap lemma yang terlibat. pertimbangkan sesuatu seperti EXP ^ 2. Itu bisa menangani RP, RNP, dll sebagai lelucon. Anda tidak bepergian dengan hierarki dengan mudah.

Steve Uurtamo

Jawaban:

Kebenaran suatu pernyataan berbeda dengan kebenaran yang memiliki bukti (pendek) dalam sistem bukti. Bahasa ini ekspresif tetapi tidak berarti bahwa semua pernyataan yang valid dalam bahasa memiliki bukti pendek dalam sistem.

Teorema tidak mengatakan bahwa Anda dapat memeriksa kebenaran dari suatu pernyataan atau bahkan kebenaran dari bukti panjang yang sewenang-wenang atau dari teorema yang arbitrer. Ini untuk bukti keanggotaan dalam , yang menurut definisi memiliki bukti ukuran polinomial (sertifikat) keanggotaan. Teorema hanya mengatakan bahwa Anda tidak perlu membaca bukti keanggotaan penuh (ukuran polinomial) dalam untuk memutuskan kebenarannya. $\mathsf{NP}$ $\mathsf{NP}$

Salah satu implikasi dari teorema adalah menerapkannya pada himpunan teorema dalam bahasa arbitrer yang memiliki bukti pendek (yaitu polinom arbitrer) dalam sistem bukti yang efisien (yaitu dapat ditentukan dalam waktu polinomial jika string yang diberikan adalah bukti pemberian yang diberikan pernyataan). Misalnya, teorema ZFC yang memiliki bukti ukuran mana adalah ukuran rumus. Jika sistem buktinya baik, maka Anda dapat secara probabilistik memverifikasi kebenaran teorema yang memiliki bukti pendek dengan membaca sebagian kecil dari buktinya. Saya pikir ini adalah maksud maksud dari pernyataan informal " bukti yang ditulis dalam bahasa matematika yang ketat dapat diperiksa secara efisien ke tingkat akurasi yang diinginkan tanpa persyaratan membaca seluruh bukti ". $n^{100}$ $n$

Kaveh
sumber

Biarkan saya mencoba mengklarifikasi.

Pertimbangkan masalah komputasi berikut: diberi pernyataan matematis (dalam sistem aksioma favorit Anda) dan angka n yang diberikan dalam representasi unary, putuskan apakah pernyataan tersebut memiliki bukti ukuran n.

Ini adalah masalah NP: diberikan bukti, seseorang dapat secara efisien memverifikasi bahwa itu adalah ukuran n dan bahwa itu adalah bukti yang sah dari teorema. Catatan: meskipun pernyataan melibatkan kuantifier seperti UNTUK SEMUA, itu tidak berarti bahwa verifier perlu memeriksa semua kemungkinan, itu hanya berarti bahwa verifier menggunakan aturan inferensi yang melibatkan kuantifikasi UNTUK SEMUA.

Oleh karena itu, Teorema PCP berlaku untuk masalah ini, sehingga terdapat format bukti (berbeda) yang memungkinkan verifikasi probabilistik.

Catatan lain (mengenai komentar Peter): Verifikasi PCP hanya menggunakan keacakan logaritmik. Ini berarti bahwa itu dapat digantikan oleh verifikasi standar, deterministik, yang melihat seluruh bukti. Yaitu memiliki verifikasi PCP untuk suatu bahasa memasukkannya ke dalam NP.

Dana Moshkovitz
sumber