Mengapa begitu sedikit kandidat alami untuk status perantara-NP?

Diketahui oleh Teorema Ladner bahwa jika , maka ada banyak -intermediate ( ) yang tak terhingga jumlahnya . Ada juga kandidat alami untuk status ini, seperti Grafik Isomorfisme, dan sejumlah lainnya, lihat Masalah Antara P dan NPC . Namun demikian, sebagian besar di antara kerumunan yang dikenal diketahui baik dalam atau . Hanya sebagian kecil dari mereka yang tetap menjadi kandidat untuk . Dengan kata lain, jika kita memilih secara acakN P N P I natural N P P N P C N P I N ${\mathsf P}\neq \mathsf {NP}$$\mathsf {NP}$$\mathsf{NPI}$$natural$ $\mathsf {NP}$$\mathsf {P}$$\mathsf {NPC}$$\mathsf {NPI}$$\mathsf {NP}$-masalah di antara yang diketahui, kami memiliki sedikit kesempatan untuk memilih . Apakah ada penjelasan untuk fenomena ini?$\mathsf {NPI}$

Saya bisa memikirkan 3 penjelasan yang mungkin, lebih pada sisi filosofis:

1. Alasan untuk memiliki seperti sebagian kecil dari alam calon adalah bahwa akhirnya akan berubah menjadi kosong. Saya tahu, ini menyiratkan , jadi sangat tidak mungkin. Namun demikian, orang masih dapat berdebat (meskipun saya bukan salah satu dari mereka) bahwa masalah alami adalah pengamatan empiris yang tampaknya benar-benar mendukung , sebaliknya untuk sebagian besar pengamatan lainnya.N P I P = N P N P I P = N $\mathsf {NPI}$$\mathsf {NPI}$${\mathsf P} =\mathsf {NP}$$\mathsf {NPI}$${\mathsf P} =\mathsf {NP}$

2. Kecilnya "natural- " mewakili semacam transisi fase yang tajam antara masalah mudah dan sulit. Tampaknya, masalah algoritmik alami yang bermakna berperilaku sedemikian rupa sehingga cenderung mudah atau sulit, transisinya sempit (tetapi masih ada).$\mathsf {NPI}$

3. Argumen dalam 2 dapat diambil secara ekstrem: pada akhirnya semua masalah dalam "natural- " akan dimasukkan ke , namun , jadi . Ini berarti bahwa semua masalah yang tersisa diP ∪ N P C P ≠ N P N P I ≠ ∅ N P $\mathsf {NPI}$$\mathsf {P} \cup \mathsf {NPC}$${\mathsf P}\neq \mathsf {NP}$$\mathsf {NPI}\neq \emptyset$$\mathsf {NPI}$"tidak wajar" (dibuat-buat, tanpa makna kehidupan nyata). Penafsiran ini bisa jadi masalah alam mudah atau sulit; transisi hanyalah konstruksi logis, tanpa makna "fisik". Ini agak mengingatkan pada kasus bilangan irasional, yang sangat logis, tetapi tidak muncul sebagai nilai yang diukur dari setiap kuantitas fisik. Dengan demikian, mereka tidak datang dari realitas fisik, mereka lebih pada "penutupan logis" dari realitas itu.

Penjelasan mana yang paling Anda sukai, atau dapatkah Anda menyarankan yang lain?

Seperti yang telah ditunjukkan orang lain, masih bisa diperdebatkan sejauh mana hal yang Anda coba jelaskan adalah benar. Orang bisa berpendapat bahwa, pada tahun 60-an dan 70-an, para ilmuwan komputer teoretis hanya lebih tertarik pada jenis masalah yang berubah menjadi P atau NP-lengkap. Hari ini, karena munculnya kompleksitas-teoritik kriptografi, komputasi kuantum, kisi, dll .--- serta fakta sederhana bahwa kelengkapan NP telah menjadi sangat dipahami --- kita menjadi semakin tertarik pada macam-macam masalah yang berubah menjadi NP-intermediate.

Namun, orang dapat bertanya: sejauh hal itu benar --- yaitu, sejauh banyak masalah pencarian dan pengoptimalan "snap" menjadi NP-complete atau yang lain di P --- sejauh itu , mengapa itu benar? Di sini, saya pikir Anda bisa mendapatkan banyak intuisi dengan melihat fenomena sebelumnya dari komputabilitas: bahwa begitu banyak model alami perhitungan "jepret" menjadi Turing-complete. Dalam hal ini, saya akan mengatakan penjelasannya adalah, sekali Anda memiliki beberapa komponen dasar --- memori baca / tulis, loop, kondisional, dll .- sulit untuk menghindarimampu mensimulasikan mesin Turing, dan karenanya menjadi Turing-lengkap. Dalam banyak cara yang sama, setelah masalah pencarian atau optimasi Anda memiliki beberapa komponen dasar --- yang paling penting, kemampuan untuk membangun "gadget" yang menyerupai gerbang logika seperti AND, ATAU, dan TIDAK --- sulit untuk menghindari kemampuan untuk menyandikan SAT dan karena itu menjadi NP-lengkap.

Cara saya suka memikirkannya, masalah seperti SAT mengerahkan "tarikan gravitasi" yang kuat pada semua masalah komputasi lain di sekitarnya, membuat mereka ingin "mengambil" menjadi NP-complete juga. Jadi, biasanya bahkan tidak memerlukan penjelasan khusus ketika masalah lain menyerah pada tarikan itu! Yang lebih mencolok, dan lebih membutuhkan penjelasan, adalah ketika masalah NP (tampaknya) sulit memiliki beberapa sifat yang memungkinkannya menahan tarikan gravitasi SAT. Kami kemudian ingin tahu: apa adalah properti itu? Mengapa Anda tidak bisa memainkan trik kelengkapan NP biasa untuk masalah ini, membangun gadget yang menyandikan gerbang logika Boolean? Saya membuat daftar beberapa jawaban umum untuk pertanyaan itu dalam jawaban CS.SE baru-baru ini, tetapi (seperti yang ditunjukkan komentator lain) ada kemungkinan jawaban lain yang saya lewatkan.

Banyak masalah alami dapat dinyatakan sebagai Masalah Kepuasan Kendala, dan ada teorema dikotomi untuk CSP.

Hanya lelucon: setelah memikirkan "tarikan gravitasi SAT" dalam jawaban bagus Scott Aaronson, metafora lain muncul di benak saya: sandwich 3-SAT 2-SAT !

... tapi saya tidak tahu apakah sandwich dapat diisi dengan bahan-bahan alami (namun saya menemukan bahwa itu bisa diisi dengan beberapa - Saus SAT [1] jika Hipotesis Eksponensial-Waktu benar) :-D$(2 + \frac{(\log n)^k}{n^2})$

Hasil lain dalam [1] adalah tidak dapat diisi dengan .$(2+1/n^{2−\epsilon}),0<\epsilon<2$

[1] Yunlei Zhao, Xiaotie Deng, CH Lee, Hong Zhu, -SAT dan propertinya$(2+f(n))$ , Matematika Terapan Terpisah, Volume 136, Edisi 1, 30 Januari 2004, Halaman 3-11, ISSN 0166 -218X.

Kita tidak bisa mengesampingkan kemungkinan lain bahwa ada banyak masalah alami . Kelangkaan yang tampak adalah karena kurangnya teknik dan alat yang diperlukan untuk membuktikan status -intermediate di bawah beberapa dugaan kompleksitas yang masuk akal (Arora dan Barak mencatat bahwa kita tidak dapat membuktikan status -intermediate dari setiap masalah alami bahkan dengan asumsi ).N P N P N P P ≠ N $NP$$NP$$NP$$NP$$P \ne NP$

Tampaknya pintu air masalah intermediate alami terbuka. Jonsson, Lagerkvist, dan Nordh memperluas teknik diagonalisasi Ladner, yang dikenal sebagai meniup lubang masalah , dan menerapkannya pada Masalah Kepuasan Kendala. Mereka memperoleh CSP yang merupakan kandidat untuk status -intermediate. Mereka membuktikan bahwa masalah penculikan proposisional memiliki fragmen intermediate.N P N $NP$$NP$$NP$

Juga, Grohe membuktikan adanya masalah CSP intermediate dengan asumsi bahwa . Dia mendapatkan masalah seperti itu dengan membatasi lebar pohon dari grafik primal yang sesuai.F P T ≠ W [ 1 $NP$$FPT \ne W[1]$

Referensi :

1- M. Grohe. Kompleksitas masalah homomorfisme dan kendala kepuasan dilihat dari sisi lain. Jurnal ACM, 54 (1), artikel 1, 2007

2- Peter Jonsson, Victor Lagerkvist dan Gustav Nordh. Meniup Lubang dalam Berbagai Aspek Masalah Komputasi, dengan Aplikasi untuk Memuaskan Kepuasan. Dalam Prosiding Konferensi Internasional ke-19 tentang Prinsip dan Praktek Pemrograman Kendala (CP-2013). 2013

Berikut ini adalah dongeng tentang struktur Goldilocks dari masalah NP-intermediate. (Peringatan: cerita ini mungkin merupakan kekeliruan yang berguna untuk menghasilkan dan menguji hipotesis potensial, tetapi tidak dimaksudkan untuk menjadi ilmiah yang ketat. Ini bergantung pada satu bagian Hipotesis Waktu Eksponensial, sejumput sihir kompleksitas Kolmogorov, beberapa potong dipinjam dari teori SAT pemecahan, dan trikotomi heuristik Terence Tao untuk masalah. Konsumsilah dengan risiko sendiri, seperti halnya semua ramuan melambaikan tangan tentang matematika.)

Jika hampir semua instance dalam masalah dalam NP sangat terstruktur, maka masalahnya sebenarnya dalam P. Contoh sehingga hampir semua mengandung banyak redundansi, dan algoritma waktu polinomial untuk masalah adalah cara untuk memperhitungkan redundansi. Bahkan dapat dibayangkan bahwa setiap masalah dalam P dapat diperoleh dengan mengambil beberapa masalah dalam EXP dan menambahkan beberapa redundansi terstruktur, melalui beberapa bentuk padding (belum tentu jenis biasa). Jika demikian, maka algoritma waktu polinomial dapat dilihat sebagai cara yang efisien untuk membatalkan lapisan itu.

Jika ada cukup contoh yang tidak terstruktur, membentuk "inti kekerasan", maka masalahnya adalah NP-lengkap.

Namun, jika "inti kekerasan" ini terlalu jarang, maka ia hanya memiliki ruang untuk mewakili sebagian SAT, sehingga masalahnya ada pada P atau NP-intermediate. (Argumen ini adalah inti dari teorema Ladner). Untuk menggunakan analogi Scott, "inti dari kekerasan" memberikan tarikan gravitasi pada masalah, ke arah itu menjadi NP-lengkap. Contoh dalam "inti kekerasan" tidak mengandung banyak redundansi, dan satu-satunya algoritma realistis yang bekerja untuk semua contoh tersebut adalah pencarian brute force (tentu saja, jika hanya ada banyak, maka pencarian tabel juga berfungsi).

Dari perspektif ini, masalah NP-intermediate harus jarang terjadi, karena mereka membutuhkan keseimbangan Goldilocks yang baik antara instance yang terstruktur dan tidak terstruktur. Instans harus memiliki redundansi yang cukup sehingga sebagian dapat diterima oleh suatu algoritma, tetapi harus ada inti kekerasan yang cukup sehingga masalahnya bukan pada P.

Orang bisa menceritakan kisah yang lebih sederhana (dan lucu, tetapi juga berpotensi lebih menyesatkan) berdasarkan teka-teki. Dengan hanya beberapa kendala, seseorang dapat memaksa banyak pencarian untuk dilakukan, misalnya NxN Sudoku adalah NP-complete. Sekarang pertimbangkan untuk diminta untuk memecahkan banyak teka-teki kecil sebagai satu contoh, dalam sekali jalan (misalnya banyak 9x9 Sudokus). Waktu yang dibutuhkan kira-kira akan linier dalam jumlah teka-teki pada setiap contoh, dan masalah ini kemudian pada P. Untuk masalah antara, orang dapat menganggap setiap contoh sebagai jumlah Sudokus yang besar (tapi tidak terlalu besar) pada largish grid (tapi tidak terlalu besar). Alasan kami tidak mengamati banyak masalah seperti itu adalah karena mereka suram untuk berpose dan menyelesaikannya!

$\mathsf{NPI}$$\mathsf{NPI}$$\mathsf{NP}$

$n$$\geq \log n$$\mathsf{NPI}$ $\mathsf{NP}$$x$$Q$$x$$Q$$\mathsf{NPI}$$\mathsf{P}$

$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{NPI}$$\mathsf{NPC}$

$\mathsf{NPI}$$\mathsf{P}$