Apakah P / poli

$P/poly = NP/poly$ menyiratkan $NP \subseteq P/poly$ , yang pada gilirannya memiliki konsekuensi yang menarik seperti runtuhnya hierarki polinomial.

Apakah ada implikasi yang menarik untuk $P/poly \neq NP/poly$ ?

cc.complexity-theory conditional-results advice-and-nonuniformity Thomas Klimpel
sumber

P / p o l y = N P / p o l y

$\mathrm{P}/\mathrm{poly}=\mathrm{NP}/\mathrm{poly}$ adalahsetaradengan

N P \subseteq P / p o l y

$\mathrm{NP}\subseteq\mathrm{P}/\mathrm{poly}$ .

Emil Jeřábek 3.0

@ EmilJeřábek Jadi Anda mengatakan P / poli

\neq

$\neq$ NP / poli menyiratkan NP

⊈

$\not\subseteq$ P / poli. Apakah Anda memiliki referensi untuk ini, atau dapatkah Anda menjelaskan kepada saya bagaimana cara melihatnya? Jika ya, maka ini secara definitif memenuhi syarat sebagai jawaban.

Thomas Klimpel

@ Kaveh: apakah menghilangkan motivasi benar-benar hal yang harus kita lakukan? Itu mengenalkan saya pada hal-hal yang belum pernah saya temui sebelumnya, dan itu tidak seperti itu tidak dipotong. Ini bukan Twitter.

András Salamon

@ EmilJeřábek Saya rasa saya mengerti sekarang. NP

\subseteq

$\subseteq$ P / poly menyiratkan P / poly = NP / poly, karena algoritma deterministik bisa mendapatkan string saran sendiri untuk menjadi sama kuatnya dengan NP, bersama-sama dengan string-saran untuk bahasa dari NP / poly, dan ini adalah cukup untuk memutuskan bahasa itu.

Thomas Klimpel

@ThomasKlimpel: Ya, persis.

Emil Jeřábek 3.0

Komentar Emil Jeřábek menjawab pertanyaan:

P / poly NP / poly setara dengan NP P / poly $=$ $\subseteq$

Perhatikan akibat wajarnya

P / poly NP / poly menyiratkan P NP. $\neq$ $\neq$

Bukti wajar:

P / poly NP / poly setara dengan NP P / poly (komentar Emil) $=$ $\subseteq$ $\$
NP P / poly menyiratkan P / poly NP / poly (tersirat oleh 1.) $\subseteq$ $=$ $\$
P / poly NP / poly menyiratkan NP P / poly (setara dengan 2.) $\neq$ $\not\subseteq$ $\$
NP P / poly menyiratkan P NP (P P / poly) $\not\subseteq$ $\neq$ $\$ $\subseteq$
P / poly NP / poly menyiratkan P NP (tersirat oleh 3. dan 4.) $\neq$ $\neq$ $\$

Bukti komentar Emil: Cukup untuk menunjukkan bahwa NP P / poly menyiratkan P / poly NP / poly. $\subseteq$ $=$

Jadi mari kita asumsikan NP P / poly. $\subseteq$
Karena SAT NP terdapat dan serangkaian nasehat string dengan , suatu algoritma deterministik yang dapat tentukan SAT instance ukuran dalam waktu , jika ia memiliki akses ke . WLOG, algoritme itu juga dapat menentukan instance SAT dari ukuran , karena kita dapat mendefinisikan urutan yang dimodifikasi dengan , di mana semua string saran sebelumnya termasuk dalam . $\in$ $p_{SAT}\geq k_{SAT}>0$ $s_n$ $\left|s_n\right|\leq n^{k_{SAT}}$ $n$ $\leq n^{p_{SAT}}$ $s_n$ $\leq n$ $s'_n=s'_{n-1}s_n$ $\left|s'_n\right|\leq n^{k_{SAT}+1}$ $s'_n$
Sekarang mari NP / poly menjadi bahasa yang arbitrer, yang kita perlu menunjukkan P / poly. Ada ada dan urutan string saran dengan algoritma non-deterministik yang dapat memutuskan dan contoh ukuran dalam waktu , jika ia memiliki akses ke . $L\in$ $L\in$ $p_L\geq k_L>0$ $l_n$ $\left|l_n\right|\leq n^{k_L}$ $L$ $n$ $\leq n^{p_L}$ $l_n$
Untuk setiap dengan , sebuah SAT contoh dari ukuran dapat dihitung (dalam waktu ) yang satisfiable persis jika . $w$ $|w|=n$ $\leq c\cdot n^{p_L}$ $O(n^{p_L})$ $w\in L$
Jadi untuk urutan nasehat string dengan , kombinasi dari algoritma deterministik dari 2. dan 4. memberikan algoritma deterministik yang dapat menentukan contoh ukuran dalam waktu , jika memiliki akses ke . $t_n=l_ns_{c\cdot n^{p_L}}$ $|t_n|\leq n^{k_L}+(c\cdot n^{p_L})^{k_{SAT}}$ $L$ $n$ $O((c\cdot n^{p_L})^{p_{SAT}})$ $t_n$
Karena NP / poly adalah bahasa yang arbitrer, ini menunjukkan NP / poly P / poly, dengan asumsi bahwa NP P / poly. $L\in$ $\subseteq$ $\subseteq$

Semua bukti di atas relativize, karena keberadaan masalah NP-lengkap juga berlaku di dunia relativized. Ini menunjukkan bahwa sia-sia untuk mencari bukti bahwa P / poly NP /. Namun mari kita meringkas bagian motivasi yang dihapus $\neq$ dari pertanyaan sebagai "String saran bisa menjadi sistem aksiomatik formal (otomatis dijamin konsisten, seringai jahat) yang kekuatannya dengan cepat meningkat dengan panjang input, dan NP sangat pandai mengeksploitasi saran ini." Jika seseorang tidak terlalu berhati-hati bahwa "keberadaan urutan nasihat menyengat" hanya memiliki makna "formal" relatif terhadap sistem formal yang tetap, pengaturan itu kemungkinan akan memungkinkan konstruksi paradoks yang jelas. Namun konstruksi paradoks semacam itu mungkin menyenangkan, dan mungkin mereka bahkan menyarankan cara bagaimana membangun bukti independensi (untuk sistem formal yang cukup lemah).

Thomas Klimpel
sumber

Apakah P / poli

Jawaban: