Apa alasan "nyata" bahwa IP = PSPACE tidak merelatifkan?

IP = PSPACE terdaftar sebagai contoh kanonik dari hasil non-relativizing, dan bukti untuk ini adalah bahwa ada oracle sedemikian sehingga , sementara untuk semua nubuat . $O$ ${\sf coNP}^O \not\subseteq {\sf IP}^O$ ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ $O$

Namun, saya telah melihat hanya beberapa orang yang memberikan penjelasan "langsung" untuk mengapa hasil ${\sf IP} = {\sf PSPACE}$ tidak -relativize, dan jawaban yang biasa adalah "arithmetization". Setelah memeriksa bukti IP = PSPACE, jawaban itu tidak salah , tetapi tidak memuaskan bagi saya. Tampaknya alasan "nyata" melacak dirinya kembali ke bukti bahwa masalah TQBF - rumus boolean terkuantifikasi benar - lengkap untuk PSPACE; untuk membuktikan itu, Anda perlu menunjukkan bahwa Anda dapat menyandikan konfigurasi mesin PSPACE dalam format berukuran polinom, dan (ini tampaknya menjadi bagian yang tidak relativizing) Anda dapat menyandikan transisi yang "benar" antara konfigurasi dalam ukuran polinomial rumus boolean - ini menggunakan langkah gaya Cook-Levin.

Intuisi yang saya kembangkan adalah bahwa hasil non-relativizing adalah hasil yang mengaduk-aduk sepintas lalu dari Turing Machines, dan langkah di mana TQBF terbukti lengkap untuk PSPACE adalah di mana hal ini terjadi - dan langkah aritmetisasi bisa Hanya terjadi karena Anda memiliki rumus boolean eksplisit untuk berhitung.

Bagi saya ini adalah alasan mendasar mengapa IP = PSPACE tidak merelatifkan; dan mantra cerita rakyat bahwa teknik aritmetisasi tidak merelatifkan tampaknya merupakan produk sampingan dari itu: satu-satunya cara untuk menghitung sesuatu adalah jika Anda memiliki formula boolean yang mengkodekan sesuatu tentang TMs di tempat pertama!

Apakah ada sesuatu yang saya lewatkan? Sebagai subquestion - apakah ini berarti semua hasil yang menggunakan TQBF dalam beberapa cara juga tidak relativize?

cc.complexity-theory interactive-proofs relativization Henry Yuen
sumber

Anda dapat memasukkan gerbang oracle dalam formula Boolean yang dikuantifikasi, dan kemudian TQBF yang relativized seperti itu O selesai untuk PSPACE ^ O, jadi ini bukan langkah non-relativizing.

Emil Jeřábek mendukung Monica

Hai Emil - bisakah Anda sedikit lebih rumit? Katakanlah saya memiliki mesin M, dan saya mencoba melakukan bukti yang sama bahwa L (M) (bahasa yang diterima oleh M) dapat direduksi menjadi (apa pun ). Saya akhirnya harus membuat rumus boolean yang menyatakan apakah dua konfigurasi C, C 'dari mesin oracle M adalah tetangga (untuk dua konfigurasi C, C'). Bagaimana saya bisa memastikan, terlepas dari ramalannya, formula boolean ini memiliki ukuran yang terbatas, apalagi berukuran polinomial? Misalnya, O dapat menyandikan Masalah Pemutusan.

{P S P A C E}^{O}

${\sf PSPACE}^O$

T B Q F^{O}

$TBQF^O$

T B Q F^{O}

$TBQF^O$

Henry Yuen

Saya kira saya bisa mendorong ini lebih jauh lagi - apakah teorema Cook-Levin sendiri relativize? Untuk alasan yang sama yang disebutkan di atas, saya rasa tidak. Apakah teorema Cook-Levin relativizes menentukan apakah bukti kelengkapan PSPACE dari TQBF juga merelatifikasi.

Henry Yuen

Rumus QBF ^ O dapat, terlepas dari penghitung biasa dan penghubung Boolean, juga menggunakan gerbang fan-in tanpa batas yang baru, sebut saja , yang semantiknya adalah jika dan hanya jika string milik oracle . Mengekspresikan dalam bahasa ini bahwa satu konfigurasi adalah penerus dari yang lain adalah latihan yang sederhana, karena Anda bisa cukup menyambungkan isi rekaman permintaan oracle ke . (Saya berasumsi di sini bahwa mesin PSPACE hanya dapat membuat kueri panjang secara polinomi.)

f (x_{0}, \dots, x_{n})

$f(x_0,\dots,x_n)$

f (x_{0}, \dots, x_{n}) = 1

$f(x_0,\dots,x_n)=1$

x_{0} \dots x_{n}

$x_0\dots x_n$

O

$O$

f

$f$

Emil Jeřábek mendukung Monica

Saya mengerti - Anda mengatakan bahwa ketika merelatifkan bukti kelengkapan PSPACE dari TQBF, Anda tidak hanya meratifikasi mesin yang sedang bermain, tetapi Anda juga merelatifkan sendiri rumus boolean (jadi mereka bukan lagi rumus boolean dalam arti yang ketat) ). Dalam hal ini, saya bisa melihat mengapa langkah aritmatisasi akan rusak. Terima kasih! Mungkin Anda bisa menuliskannya sebagai jawaban.

Henry Yuen

Jawaban apa pun untuk pertanyaan tentang formulir, "Apa alasan sebenarnya bahwa ..." tentu akan agak subyektif. Namun, untuk kasus IP = PSPACE tertentu, saya pikir kasus yang cukup bagus dapat dibuat bahwa aritmetisasi memang kuncinya, dengan mengamati bahwa sementara IP = PSPACE tidak mengalami relativisasi , ia melakukan algebrize dalam arti Aaronson dan Wigderson . Saat mereka menjelaskan dalam makalah mereka, secara kasar, inklusi kelas kompleksitas algebrize jika untuk semua nubuat dan semua ekstensi derajat rendah dari ${\cal C} \subseteq {\cal D}$ ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ $A$ $\tilde A$ $A$ . Secara khusus, mereka menunjukkan bahwa inklusi PSPACE IP algebrize, meskipun tidak relativize. $\subseteq$

Intuisi yang saya kembangkan adalah bahwa hasil non-relativizing adalah yang menyodok dengan sepele sepele Mesin Turing

Ini bukan intuisi yang buruk, tapi saya berpikir bahwa Aaronson-Wigderson hasil menunjukkan bahwa IP = bukti PSPACE pokes sekitar dengan cara yang agak terbatas, dan tentu saja tidak dengan cara yang cukup canggih untuk membuktikan P NP, karena Aaronson dan Wigderson juga menunjukkan bahwa teknik non-algebrizing akan diperlukan untuk memisahkan P dari NP. $\ne$

Timothy Chow
sumber

Terima kasih untuk referensi. Biarkan saya melihat apakah saya memahami ini: apa yang Anda - dan makalah Aaronson / Wigderson - tampaknya berpendapat adalah bahwa "arithmetization" adalah langkah lemah yang tidak merelatifkan, dan bahwa perubahan kecil, alami pada gagasan relativization (yaitu, relativization aljabar) akan merusak properti ini. Karena sisa IP = bukti PSPACE adalah relativizing (dan saya yakin dengan apa yang Emil katakan di atas), itu berarti IP = hasil PSPACE itu sendiri sangat lemah non-relativizing, yang adalah apa yang Anda katakan. Sangat menarik! Terima kasih. Saya perlu cara menerima kedua jawaban :)

Henry Yuen

Ya, itu pada dasarnya benar.

Timothy Chow

Apa alasan "nyata" bahwa IP = PSPACE tidak merelatifkan?

Jawaban: