Masalah dalam NP tetapi tidak dalam Average-P / poly

The Karp – Lipton Theoem menyatakan bahwa jika , maka runtuh menjadi . Oleh karena itu, dengan asumsi pemisahan antara dan , no - masalah lengkap akan menjadi milik . $\mathsf{NP} \subset \mathsf{P/poly}$ $\mathsf{PH}$ $\mathsf{\Sigma^P_2}$ $\mathsf{\Sigma^P_2}$ $\mathsf{\Sigma^P_3}$ $\mathsf{NP}$ $\mathsf{P/poly}$

Saya tertarik dengan pertanyaan berikut:

Dengan asumsi bahwa tidak runtuh, atau dengan asumsi setiap asumsi yang masuk akal lainnya dalam kompleksitas struktural, apa hard-on-rata masalah yang terbukti tidak terletak pada (jika ada)? $\mathsf{PH}$ $\mathsf{NP}$ $\mathsf{Average\mbox{-}P/poly}$

Definisi dapat ditemukan di Hubungan antara kasus-Rata-rata dan Kompleksitas kasus-terburuk . Terima kasih kepada Tsuyoshi karena menunjukkan bahwa saya benar-benar perlu menggunakan alih-alih . $\mathsf{Average\mbox{-}P/poly}$ $\mathsf{Average\mbox{-}P/poly}$ $\mathsf{P/poly}$

Saya pikir ada masalah seperti (versi keputusan) FAKTOR atau DLOG yang diduga terletak di , tetapi dugaan tersebut tidak terbukti berdasarkan pada pemisahan antara kelas kompleksitas. (Tolong koreksi saya jika saya salah.) $\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$

cc.complexity-theory np conditional-results advice-and-nonuniformity average-case-complexity MS Dousti
sumber

(1) Saya tidak berpikir bahwa asumsi bahwa hierarki polinom tidak runtuh diketahui menyiratkan bahwa ada masalah sulit rata-rata dalam NP. Bagian 18.4 dari Arora dan Barak menyatakan: "[...] meskipun kita tahu bahwa jika P = NP, maka hierarki polinomial PH runtuh menjadi P [...], kami tidak memiliki hasil analog dengan kompleksitas kasus rata-rata."

Tsuyoshi Ito

(2) Apakah P / poli dalam pertanyaan yang biasa dengan kompleksitas kasus terburuk, atau apakah Anda mempertimbangkan analog kasus rata-rata? Jika ini adalah yang terburuk, maka Anda memerlukan DistP ≠ DistNP dan NP⊈P / poly untuk memiliki masalah seperti itu, dan jika ini berlaku, maka setiap masalah yang menyelesaikan DistNP memenuhi persyaratan karena masalah yang menyelesaikan DistNP harus NP-complete jika kita membuang distribusi input.

Tsuyoshi Ito

@ Tsuyoshi: Terima kasih banyak. Anda memang memiliki poin tentang kasus terburuk / rata-rata P / poli. Pada pemikiran kedua (tentang masalah asli), saya pikir saya harus menafsirkan P / poly sebagai kelas kasus rata-rata .

MS Dousti

Saya membaca revisi 3. Secara taktis, masalah seperti itu ada jika dan hanya jika DistNP ⊈ Average-P / poly. Dan jika DistNP ⊈ Average-P / poly, maka setiap masalah DistNP-complete berada di luar Average-P / poly karena Average-P / poly ditutup dengan pengurangan (antara masalah distribusi). Tetapi mungkin Anda meminta masalah yang lebih alami dengan asumsi yang lebih kuat.

Tsuyoshi Ito

@ Tsuyoshi: Terima kasih. Bisakah Anda membuat komentar menjadi jawaban sehingga saya bisa menerimanya?

MS Dousti

Ini adalah versi yang sedikit lebih baik dari dua komentar saya tentang gabungan pertanyaan.

Mari kita batasi perhatian kita pada masalah distribusi di DistNP (alias (NP, P-computable)) untuk kesederhanaan. Kemudian Anda mencari masalah di DistNP ∖ Average-P / poly. Secara taktis, masalah seperti itu ada jika dan hanya jika DistNP ⊈ Average-P / poly. Dan jika DistNP ⊈ Average-P / poly, maka setiap masalah DistNP-lengkap berada di luar Average-P / poly karena Average-P / poly ditutup di bawah pengurangan kasus rata-rata.

(Mempertimbangkan SampNP kelas yang lebih besar (alias (NP, P-samplable) ) bukannya DistNP tidak banyak mengubah situasi karena DistNP ⊆ Average-P / poly jika dan hanya jika SampNP ⊆ Average-P / poly. Kesetaraan ini adalah langsung akibat dari Impagliazzo dan Levin [IL90] bahwa setiap masalah distribusi di SampNP adalah kasus rata-rata yang dapat direduksi menjadi beberapa masalah distribusi di DistNP.)

Saya tidak tahu asumsi alami mana yang menyiratkan DistNP ⊈ Average-P / poly. Asumsi bahwa hierarki polinom tidak runtuh tidak diketahui menyiratkan bahkan konsekuensi yang lebih lemah bahwa DistNP ⊈ Average-P, menurut Bagian 18.4 dari Arora dan Barak [AB09]: “[…] meskipun kita tahu bahwa jika P = NP , maka hierarki polinomial PH runtuh ke P [...], kami tidak memiliki hasil analog untuk kompleksitas kasus rata-rata. "

Referensi

[AB09] Sanjeev Arora dan Boaz Barak. Kompleksitas Komputasi: Suatu Pendekatan Modern , Cambridge University Press, 2009.

[IL90] Russell Impagliazzo dan Leonid A. Levin. Tidak ada cara yang lebih baik untuk menghasilkan instance NP keras daripada memilih secara seragam secara acak. Dalam Simposium Tahunan ke-31 tentang Yayasan Ilmu Komputer , 812–821, Oktober 1990. http://dx.doi.org/10.1109/FSCS.1990.89604

Tsuyoshi Ito
sumber

Masalah dalam NP tetapi tidak dalam Average-P / poly

Jawaban:

Referensi