Bukti, Hambatan dan P vs NP

Telah diketahui dengan baik bahwa bukti apa pun yang menyelesaikan pertanyaan P vs NP harus mengatasi relativization , bukti alami dan hambatan algebrization . Diagram berikut ini membagi "ruang bukti" menjadi beberapa wilayah. Sebagai contoh, sesuai dengan set bukti yang merelatifkan dan menaturalisasi. (Geometric Complexity Theory) tentu saja merupakan wilayah yang sepenuhnya di luar.$RN$$GCT$

Sebutkan beberapa bukti bersama dengan daerah yang paling terkenal milik mereka. Tempatkan mereka dengan cara terbaik yaitu, jika bukti diketahui relativize, naturalisasi dan algebrize maka itu harus ditempatkan di bukan hanya di . Jika suatu bukti relativizes tetapi tidak menaturalisasi itu milik dan seterusnya.$RNA$$RN$$R$ ${\setminus}$ $N$

Saya pikir Anda perlu menggambar ulang diagram Venn Anda ... setiap penahanan kelas kompleksitas yang relativize juga akan algebrize, setidaknya dalam arti Aaronson dan Wigderson. Artinya, akses ke "ekstensi tingkat rendah" dari oracle hanya lebih kuat daripada akses ke oracle. Demikian pula, setiap ramalan yang menunjukkan bahwa pemisahan membutuhkan teknik "non-algebrizing" menyiratkan bahwa teknik "non-relativizing" juga diperlukan.

Bertentangan dengan beberapa klaim sebelumnya di utas ini, algebrization dalam arti Aaronson & Wigderson tidak dikenal dengan subsume relativization. Sebagai contoh,

adalah pernyataan yang relativizes. (Bahkan ia memiliki bukti relativizing, apa pun yang mungkin berarti bagi pembaca.) Tetapi tidak diketahui algebrize, seperti yang disinggung oleh Aaronson & Wigderson sendiri di Bagian 10.1 dari makalah mereka [1]. (Akibatnya, ketika AW memberi tahu kami bahwa dalam diagram di atas harus berada di luar , dapat dibayangkan bahwa di dalam!)$\mathsf{NEXP} \not\subset \mathsf{P/poly}$$\mathrm {A}$$\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly}$

Namun, karya Eric Bach dan saya sendiri baru-baru ini [2] memberikan rumusan algebrization yang melakukan subsati relativization. Pada dasarnya, jika kita mengambil AW dari oracle aljabar --- dilambangkan sebagai untuk beberapa bahasa --- dan memodifikasinya dengan bijak, maka kita dapat menghilangkan patologi seperti atas.$\tilde O$$O$$(\dagger)$

Hasilnya adalah bahwa algebrization, ketika didefinisikan dengan tepat, adalah relativization sehubungan dengan orjabar aljabar --- relativiasi aljabar, di mana setiap oracle mendapat "goyangan '' --- yang berarti adalah set kosong pada diagram di atas, maka demikian pula .$\mathrm{R} \setminus \mathrm{A}$$\mathrm{RN}$

[1] http://www.scottaaronson.com/papers/alg.pdf
[2] http://eccc.hpi-web.de/report/2016/040/

PS: Formulasi lain untuk algebrization diusulkan oleh Impagliazzo, Kabanets dan Kolokolova sebelumnya, yang juga menempatkan di dalam , tetapi tidak diketahui sekuat gagasan AW. Lihat kertas saya dengan Eric untuk perbandingan.$\mathrm{R}$$\mathrm{A}$

The teorema ruang dan waktu hirarki merelatifkan. Mereka seragam, jadi mereka tampaknya tidak menaturalisasi.

Saya pikir hasil diagonalisasi tidak langsung seperti TimeSpace batas bawah Lance Fortnow, et al. dan juga hasil Ryan Williams tidak relativize karena mereka bukan kotak hitam (tapi saya tidak yakin tentang ini). Buktinya tampaknya tidak menaturalisasi karena mereka menggunakan teorema hierarki.

Bukti-bukti permanen tidak berseragam$TC^0$ menggunakan teorema hierarki dan tampaknya tidak berfungsi untuk kasus tidak seragam, dan tampaknya tidak menaturalisasi. Di sisi lain, saya tidak tahu apakah mereka relativisasi, mereka mungkin dengan gagasan relativiasi yang sesuai.

Bukti interaktif tidak mengalami relativisasi. Saya tidak berpikir mereka menaturalisasi karena mereka seragam.