Apakah diagonalisasi menangkap esensi dari pemisahan kelas?

Saya tidak ingat pernah melihat pemisahan kelas yang tidak didasarkan pada hasil diagonalisasi dan relatisasi. Diagonisasi masih dapat digunakan untuk memisahkan kelas yang diketahui yang tersisa, karena argumen non-relativiasi mungkin masih digunakan dalam kesimpulan diagonalisasi, atau dalam konstruksi mesin Turing yang didiagonalisasi. Berikut beberapa pertanyaan terkait:

Apakah ada bukti pemisahan kelas yang tidak didasarkan pada diagonalisasi?

Dan jika demikian

Bisakah kita menemukan mekanisme referensi diri di belakang mereka?

Lebih lanjut,

apakah setiap pemisahan kelas memiliki bukti "alami kanonik" (dalam pengertian informal)?

Jika demikian, kita harus mencoba menemukan argumen yang tidak relativizing, daripada skema bukti lain untuk pertanyaan terbuka.

Bisakah setiap bukti non-diagonal ditulis ulang menjadi diagonal?

Tergantung pada bagaimana Anda memformalkan diagonalisasi. Kozen memiliki makalah yang menunjukkan pemisahan kelas yang rumit harus menjadi bukti diagonalisasi.

Sejak diagonalisasi relativizes, setiap hasil kompleksitas menyiratkan relativiasi kontradiktif tidak dapat didasarkan pada diagonalisasi. Mengutip Arora-Barak :

$O$$O \subseteq \{0, 1\}^*$

$P$$NP$$P\ne NP$

$P^{PH} \subseteq IP$

Untuk menambah jawaban Fortnow, melanjutkan pekerjaan Kozen, Nash, Impagliazzo, dan Remmel memformalkan gagasan diagonalisasi yang kuat dan memberikan beberapa bukti bahwa itu tidak relativize. Untuk sebagian menjawab pertanyaan pertama Anda, hasilnya menunjukkan bahwa beberapa bukti pemisahan kelas tidak dapat didasarkan pada diagonalisasi yang kuat. Berikut ini abstraknya:

Kami mendefinisikan dan mempelajari diagonalisasi yang kuat dan membandingkannya dengan diagonisasi yang lemah, tersirat dalam [7]. Hasil Kozen dalam [7] menunjukkan bahwa hampir setiap pemisahan dapat disusun kembali sebagai diagonalisasi yang lemah. Kami menunjukkan bahwa ada kelas bahasa yang tidak dapat dipisahkan oleh diagonalisasi yang kuat dan memberikan bukti bahwa diagonalisasi yang kuat tidak terelatifikasi. Kami juga mendefinisikan dua jenis diagonalisasi tidak langsung dan mempelajari kekuatan mereka.

Karena kami mendefinisikan diagonalisasi yang kuat dalam hal bahasa universal, kami mempelajari kompleksitasnya. Kami membedakan dan membandingkan bahasa universal yang lemah dan ketat. Akhirnya kami menganalisis beberapa varian bahasa universal yang tampaknya lebih lemah, yang kami sebut bahasa pseudouniversal, dan menunjukkan bahwa di bawah kondisi penutupan yang lemah mereka dengan mudah menghasilkan bahasa universal.

1-Nash, A., Impagliazzo, R., Remmel; J. "Bahasa Universal dan Kekuatan Diagonalisasi." Konferensi IEEE Tahunan ke-18 tentang Kompleksitas Komputasi (CCC'03), hlm. 337, 2003.

Apakah ada bukti pemisahan kelas yang tidak didasarkan pada diagonalisasi?

Ya, ada, tetapi tidak untuk kelas kompleksitas yang seragam. Kami tidak memiliki argumen untuk mengesampingkan bukti seperti itu, tetapi sejauh ini semua pemisahan antara kelas kompleksitas seragam tampaknya menggunakan diagonalisasi di beberapa tempat.

Bisakah kita menemukan mekanisme referensi diri di belakang mereka?

Saya tidak berpikir pemisahan kelas kompleksitas tidak seragam dapat berubah menjadi argumen "referensi diri" karena mereka bukan kelas yang seragam dan tidak dapat disebutkan, dan untuk argumen referensi diri kita perlu menghitung anggota kelas.

apakah setiap pemisahan kelas memiliki bukti "alami kanonik" (dalam pengertian informal)?

Tergantung pada apa yang Anda maksud dengan "kanonik". AFAIK, tidak ada konsensus pada jawaban atas pertanyaan "ketika dua bukti pada dasarnya identik?".

Jika demikian, kita harus mencoba menemukan argumen yang tidak relativizing, daripada skema bukti lain untuk pertanyaan terbuka. Bisakah setiap bukti non-diagonal ditulis ulang menjadi diagonal?

Seperti yang telah ditunjukkan orang lain, jawabannya tergantung pada apa yang Anda maksud dengan diagonalisasi. Dalam pengertian yang lebih umum (makalah Kozen dihubungkan oleh Lance), jawabannya adalah ya untuk dua "kelas kompleksitas" yang berbeda (sebagaimana didefinisikan dalam makalah Kozen). Anda dapat mengubah argumen menjadi argumen "diagonalisasi". Tapi:

1. ini tidak berlaku untuk kelas kompleksitas yang tidak memenuhi persyaratan yang dinyatakan dalam makalah Kozen (yaitu bukan "kelas kompleks" Kozen).
2. $P$$PSpace$
3. yang penting adalah bahwa semakin umum suatu metode, semakin terbatas aplikasinya (jika digunakan dengan sendirinya) karena metode perlu bekerja untuk lebih banyak kasus dan ini adalah pembatasan pada metode, kita tidak dapat menggunakan spesifik informasi yang kami miliki tentang masalah jika tidak dibagikan atau tidak dapat diganti dengan sesuatu yang serupa untuk masalah lain yang ingin kami terapkan metode tersebut kepada mereka.
4. Kita dapat mengubah argumen pemisahan menjadi argumen "diagonalisasi" (mengingat pembatasan yang saya sebutkan di atas), tetapi fakta bahwa "fungsi diagonalisasi benar-benar memisahkan kelas" itu sendiri membutuhkan bukti. Makalah Kozen menunjukkan bahwa ada fungsi diagonalisasi jika kelasnya berbeda, tetapi bagaimana kita bisa tahu bahwa fungsi yang diberikan benar-benar mendiagonalisasi? Kami membutuhkan bukti! Dan makalah (AFAIU) tidak memberi kami ide tentang bagaimana membuat bukti itu. Jika kita memiliki argumen pemisahan, kita dapat mengubahnya menjadi bukti diagonalisasi, tetapi itu hanya setelahmemiliki bukti. Bukti asli akan berfungsi sebagai bagian dari bukti diagonalisasi baru, itu akan menunjukkan bahwa fungsi tersebut benar-benar mendiagonalisasi. (Dan dalam beberapa hal, bukti diagonalisasi yang dibangun dari kertas Kozen tidak akan menjadi "kanonik" karena itu akan sepenuhnya bergantung pada argumen aslinya.)