Apakah NPI terkandung dalam P / poly?

$\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$P ≠ N P N P I : = N P ∖ ( N P C ∪ P ) ≠ ∅ P / poli N P I ⊂ P / poli N P ⊂ N P C ∪ P /$\mathsf{PH} = \Sigma_2$$\mathsf{P} \ne \mathsf{NP}$$\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$$\mathsf{P}/\text{poly}$$\mathsf{NPI} \subset \mathsf{P}/\text{poly}$$\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly}$

Dengan asumsi (atau bahkan bahwa hierarki polinom tidak runtuh pada tingkat apa pun), adalah diketahui benar atau salah? Bukti apa yang bisa diajukan untuk dan menentangnya?N P I ⊂ P /$\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$$\mathsf{NPI} \subset \mathsf{P}/\text{poly}$

Berikut adalah alternatif yang memungkinkan untuk argumen padding, berdasarkan generalisasi Schöning tentang teorema Ladner. Untuk memahami argumen, Anda harus memiliki akses ke makalah ini (yang sayangnya akan berada di balik tembok pembayaran bagi banyak orang):

Uwe Schöning. Pendekatan seragam untuk mendapatkan set diagonal dalam kelas kompleksitas. Ilmu Komputer Teoritis 18 (1): 95-103, 1982.

Kami akan menerapkan teorema utama dari makalah itu untuk dan menjadi bahasa dan dan sebagai kelas kompleksitas sebagai berikut:$A_1$$A_2$$\mathsf{C}_1$$\mathsf{C}_2$

• $A_1 = \varnothing$ (atau bahasa apa pun di )$\mathsf{P}$
• $A_2 = \text{SAT}$
• $\mathsf{C}_1 = \mathsf{NPC}$
• $\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

Demi kejelasan, fakta yang akan kami buktikan adalah menyiratkan .N P I ⊈ P / p o l $\mathsf{NP} \not\subseteq \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Dengan asumsi bahwa kita memiliki dan . Jelas bahwa dan ditutup di bawah variasi terbatas. Makalah Schöning menyertakan bukti bahwa dapat ditampilkan secara rekursif (definisi tepat yang dapat ditemukan dalam makalah), dan bagian tersulit dari argumen adalah untuk membuktikan bahwa dapat ditampilkan secara rekursif.A 1 ∉ C 1 A 2 ∉ C 2 C 1 C 2 C 1 C$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$A_1\not\in\mathsf{C}_1$$A_2\not\in\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$

Berdasarkan asumsi-asumsi ini, teorema menyiratkan bahwa ada bahasa yang tidak ada dalam atau dalam ; dan mengingat bahwa , itu menyatakan bahwa adalah Karp-dapat direduksi menjadi , dan karena itu . Mengingat bahwa ada di tetapi bukan lengkap di , maka itu berarti .C 1 C 2 A 1 ∈ P A A 2 A ∈ N P A N P N P N P ∩ P / p o l y N P I ⊈ P / p o l $A$$\mathsf{C}_1$$\mathsf{C}_2$$A_1\in\mathsf{P}$$A$$A_2$$A\in\mathsf{NP}$$A$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP} \cap \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Tetap membuktikan bahwa dapat ditampilkan secara rekursif. Pada dasarnya ini berarti bahwa ada deskripsi eksplisit tentang urutan mesin Turing deterministik yang semuanya berhenti pada semua input dan sedemikian rupa sehingga . Jika ada kesalahan dalam argumen saya, mungkin ada di sini, dan jika Anda benar-benar perlu menggunakan hasil ini, Anda ingin melakukan ini dengan hati-hati. Bagaimanapun, dengan menyatukan semua mesin Turing nondeterministik waktu polinomial (yang dapat disimulasikan secara deterministik karena kami tidak peduli dengan waktu berjalan setiapM 1 , M 2 , ... N P ∩ P / p o l y = { L ( M k ) : k = 1 , 2 , … } M k M k M $\mathsf{NP} \cap \mathsf{P/poly}$$M_1, M_2, \ldots$$\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$$M_k$) dan semua polinomial, yang mewakili batas atas pada ukuran keluarga sirkuit Boolean untuk bahasa tertentu, saya percaya tidak sulit untuk mendapatkan enumerasi yang berfungsi. Pada dasarnya, setiap dapat menguji bahwa NTM waktu polinomialnya yang sesuai setuju dengan beberapa rangkaian ukuran polinomial hingga panjang string input yang diberikan dengan mencari semua kemungkinan sirkuit Boolean. Jika ada kesepakatan, menghasilkan seperti yang akan dilakukan oleh NTM, jika tidak maka akan ditolak (dan sebagai hasilnya mewakili bahasa yang terbatas).$M_k$$M_k$

Intuisi dasar di balik argumen (yang tersembunyi di dalam hasil Schöning) adalah bahwa Anda tidak pernah dapat memiliki dua kelas kompleksitas "baik" (yaitu, yang dengan presentasi rekursif) disjoint dan duduk flush terhadap satu sama lain. "Topologi" kelas kompleks tidak akan mengizinkannya: Anda selalu dapat membuat bahasa dengan benar di antara kedua kelas dengan entah bagaimana bergantian di antara keduanya untuk rentang panjang input yang sangat panjang. Teorema Ladner menunjukkan ini untuk dan , dan generalisasi Schöning memungkinkan Anda melakukan hal yang sama untuk banyak kelas lainnya.N P $\mathsf{P}$$\mathsf{NPC}$

Saya hanya ingin menuliskan beberapa versi argumen padding seperti yang dijelaskan dalam komentar. Saya tidak melihat mengapa celah dibutuhkan. Kami ingin menunjukkan bahwa jika NP tidak terkandung dalam P / poly maka ada masalah NP-intermediate yang tidak terkandung dalam P / poly.

Ada fungsi tanpa batas sehingga SAT tidak memiliki sirkuit dengan ukuran kurang dari , dan ada fungsi yang tidak terikat, bertambah, dan . Biarkan SAT menunjukkan bahasa yang diperoleh dengan mengisi string SAT dengan panjang hingga . Kemudian:n f ( n ) g g ( n ) = o ( f ( n ) ) n n g ( n $f$$n^{f(n)}$$g$$g(n)=o(f(n))$$n$$n^{g(n)}$

• SAT 'ada di NP (lihat di bawah!)
• SAT 'tidak dalam P / poli: diberi ukuran sirkuit untuk SAT', kita mendapatkan sirkuit ukuran untuk SAT, tetapi ini kurang dari untuk beberapa .n g ( n ) k n f ( n )$n^k$$n^{g(n)k}$$n^{f(n)}$$n$
• Tidak ada pengurangan P / poli dari SAT ke SAT ': anggap untuk kontradiksi bahwa ada sirkuit ukuran untuk SAT, yang memungkinkan gerbang SAT. Pilih cukup besar bahwa dan membiarkan . Setiap gerbang SAT di memiliki paling banyak input . Dengan menghapus input padding, kita dapat memotong gerbang SAT 'di ke gerbang SAT dengan kurang dari input, yang dapat kita simulasikan menggunakan - gerbang SAT yang dihasilkan paling banyak memiliki masukan . Mengulangi ini dan memperlakukan dengan tangan, SAT akan memiliki sirkuit dengan ukuran sekitarn k N g ( $C_n$$n^k$$N$n>NCnnkCn$g(\sqrt{N}) > 2k$$n>N$$C_n$$n^k$$C_n$ C$\sqrt{n}$ nk/2CNO(nknk/2nk/4...)≈O(n2k)nf(n)$C_{\sqrt{n}}$$n^{k/2}$$C_N$$O(n^k n^{k/2} n^{k/4} \dots) \approx O(n^{2k})$ yang kurang dari untuk beberapa .$n^{f(n)}$$n$

Edit:

Pilihan sedikit fiddly. Jika Anda senang menempatkan SAT 'dalam versi janji NP, bit ini tidak perlu.$g$

Tentukan menjadi bilangan bulat maksimum sehingga tidak ada rangkaian ukuran untuk panjang string untuk SAT. Tentukan dengan algoritma yang menghitung untuk dan berhenti setelah waktu atau ketika , dan mengembalikan lantai akar kuadrat dari nilai tertinggi yang ditemukan dalam waktu ini . Jadi tidak terikat dan dan dapat dihitung dalam waktu . Sekarang perhatikan bahwa argumen di atas hanya bergantung pada SAT yang tidak memiliki sirkuit ukuran untuk banyak sekalin f ( n ) n g ( n ) f ( m ) m = 1 , 2 , ... n m = n g ( n ) lim inf g ( n ) / f ( n ) = 0 g ( n ) n n f ( n )$f(n)$$n^{f(n)}$$n$$g(n)$$f(m)$$m=1,2,\dots$$n$$m=n$$g(n)$$\liminf g(n)/f(n)=0$$g(n)$$n$$n^{f(n)}$$n$.

Saya juga tertarik untuk melihat buktinya dengan meniup lubang di SAT seperti di http://blog.computationalcomplexity.org/media/ladner.pdf . Tanpa persyaratan NP ini cukup mudah: ada urutan sedemikian sehingga tidak ada ukuran sirkuit os mendeteksi panjang string SAT ; batasi SAT untuk string untuk beberapa .( n k ) k n n 2 2 i$n_1<n_2<\dots$$(n_k)^k$$n$$n_{2^{2^i}}$$i$

(NPI P / poly) (P NP)$\nsubseteq$$\implies$$\neq$