Teknik untuk membuktikan bahwa kalimat itu relativis

Saya tertarik pada bagaimana seseorang membuktikan bahwa kalimat itu relativis. Tentu saja, membuktikan bahwa sebuah kalimat tidak terelatifkan adalah sederhana, seperti yang terlihat dalam hasil Baker-Gill-Solovay; tetapi bagaimana seseorang membuktikan bahwa suatu kalimat memang relatif, yaitu, bahwa itu benar relatif terhadap oracle mana pun? Adakah teknik yang diketahui untuk mencapai hal ini untuk hukuman yang sewenang-wenang?

Jika Anda mengetahui referensi yang menjawab pertanyaan ini, saya ingin mendengarnya. Terima kasih.

Biasanya, cara orang membuktikan bahwa teorema kompleksitas relativizes menggunakan prosedur dua langkah berikut:

1. Buktikan teorema.

2. Amati bahwa bukti Anda menjadi relatif! Dengan kata lain, bahwa tidak ada dalam bukti yang berubah sama sekali jika semua mesin yang disebutkan dalam bukti mendapatkan akses ke oracle yang sama A.

Ya, sesederhana itu. Untuk membuatnya ketat, Anda harus menulis ulang seluruh bukti dengan menambahkan superskrip "A" di semua tempat. Namun, dalam praktiknya, jika orang memperhatikan masalah ini sama sekali, mereka biasanya hanya akan menambahkan komentar seperti "hasil ini mudah dilihat untuk direlatifkan."

Jika orang tampak angkuh tentang hal ini, itu karena mereka telah belajar, dari pengalaman, bahwa hanya teknik-teknik tertentu (seperti arithmetization) yang mungkin dapat menyebabkan bukti untuk tidak merelatifkan. Jadi, jika bukti Anda tidak menggunakan teknik-teknik itu, maka itu relatif.

(Sebuah analogi yang dekat: misalkan Anda membuktikan teorema tentang bilangan real, tetapi bukti Anda tidak pernah menggunakan apa pun tentang real selain dari fakta bahwa mereka adalah suatu bidang. Maka cukup untuk mencatat fakta itu, untuk menunjukkan bahwa sebuah teorema analog harus dipegang untuk bilangan kompleks, p-adics, dll. Tidak perlu mengulangi buktinya.)

Satu situasi di mana lebih banyak diskusi diperlukan, adalah di mana bahkan tidak jelas apa artinya merelatifkan teorema Anda. (Misalnya, apa mekanisme akses oracle?) Seperti yang ditunjukkan Kaveh di atas, tidak ada operasi matematika yang didefinisikan dengan baik untuk "merelatifkan" teorema kompleksitas, sama seperti tidak ada operasi matematika yang didefinisikan dengan baik untuk "memperumit" teorema tentang bilangan real. Perhatikan bahwa, dalam kasus terakhir, tidak cukup untuk mengganti setiap kemunculan R oleh C: Anda mungkin juga perlu mengganti x ² dengan | x | ² (di beberapa tempat, bukan yang lain!), Dan membuat perubahan lain yang "jelas" untuk ahli matematika tetapi sulit untuk mendaftar secara formal. Demikian juga, dalam teori kompleksitas, biasanyajelas apa artinya "merelatifkan" sebuah teorema (yaitu, siapa yang harus mendapatkan akses ke A, dan apa artinya bagi mereka untuk mengaksesnya?), tetapi dalam beberapa kasus itu bisa sangat halus. Lihat di sini untuk informasi lebih lanjut tentang masalah ini.

Mengubah pertanyaan Anda, orang bisa bertanya:

Apakah ada contoh teorema kompleksitas relativizing, yang mana secara signifikan lebih sulit untuk membuktikan bahwa teorema relativizes daripada bahwa teorema itu benar?

Menariknya, saya tidak dapat memberikan satu contoh pun yang tak terbantahkan (walaupun mungkin orang lain bisa)! Inilah yang terbaik yang bisa saya lakukan:

1. Pekerjaan terbaru tentang komputasi kuantum buta dan terautentikasi (oleh Broadbent-Fitzsimons-Kashefi, Reichardt-Unger-Vazirani, dan lainnya) mungkin mengarah pada contoh. Dalam kasus-kasus itu, situasinya adalah kita tidak tahu apakah teorema-teorema itu relativize atau tidak --- tetapi jika mereka melakukan relativize, maka tentu saja sebuah ide baru akan dibutuhkan di luar apa yang ada dalam bukti yang ada.

2. Dapat diperdebatkan, contoh lain mungkin adalah redukibilitas diri sendiri dari #P. Jika Anda bertanya kepada kebanyakan ahli teori kompleksitas mengapa itu benar, mereka mungkin akan mengatakan itu karena permanen adalah # P-complete dan random-reducible sendiri. Itu benar, tetapi itu tidak menjawab pertanyaan apakah #P relatif terhadap oracle. Nah, ternyata #P adalah rsr relatif terhadap oracle apa pun, dan itu bahkan tidak sulit untuk membuktikannya --- tetapi Anda perlu memberikan argumen langsung menggunakan polinomial, daripada menarik properti permanen.

3. Dalam Bagian 8 dari makalah algebrization saya dan Avi Wigderson , kami menunjukkan bahwa teorema GMW (bahwa NP memiliki bukti pengetahuan nol komputasi) adalah algebrizing. Dan itu benar - benar mengambil ide-ide baru: bukan "secara dramatis" baru, tetapi tentu saja tidak dapat ditemukan dalam bukti-bukti teorema GMW yang biasa. Tentu saja, ini untuk algebrization daripada untuk relativization.

Tambahan: Sebagai jawaban untuk pertanyaan lebih lanjut dari OP, saya tidak tahu teknik apa pun untuk menunjukkan itu, jika Anda bisa membuktikan dugaan kompleksitas tertentu (yang belum Anda lakukan), maka bukti Anda tentu akan relativize. Ya, selama Anda membatasi "pencarian bukti" Anda hanya untuk merelatifikasi teknik saja, Anda dapat yakin bahwa, jika Anda pernah berhasil menemukan bukti, maka bukti Anda tentu akan relativize. Dan dalam praktiknya, itulah yang sering dilakukan orang (misalnya, karena mereka memiliki ide-ide tertentu tentang seperti apa buktinya, dan ide-ide itu menjadi relatif). Tetapi saya tidak tahu cara apa pun untuk menjamin, apriori , bahwa dengan memperluas pencarian Anda dengan memasukkan teknik yang tidak relativiasi, Anda tidak dapat menemukan bukti yang telah menghindar dari Anda sebelumnya.