Alasan menyeluruh mengapa masalah ada di P atau BPP

Baru-baru ini, ketika berbicara dengan seorang ahli fisika, saya menyatakan bahwa dalam pengalaman saya, ketika masalah yang secara naif sepertinya membutuhkan waktu eksponensial ternyata secara nontrivial berada di P atau BPP, "alasan menyeluruh" mengapa pengurangan terjadi biasanya dapat diidentifikasi. --- dan hampir selalu, alasan itu masuk dalam daftar selusin "tersangka biasa" (misalnya: pemrograman dinamis, aljabar linier ...). Namun, itu kemudian membuat saya berpikir: bisakah kita benar-benar menuliskan daftar alasan yang layak seperti itu? Inilah upaya pertama dan tidak lengkap pada satu:

(0) Karakterisasi matematika. Masalah memiliki karakterisasi "murni-matematis" yang tidak jelas yang, begitu diketahui, membuatnya segera bahwa Anda dapat melakukan pencarian lengkap pada daftar kemungkinan pol (n). Contoh: grafik planaritas, yang diikuti oleh algoritma O (n ⁶ ) dari teorema Kuratowski.

(Seperti yang ditunjukkan "planar" di bawah, ini adalah contoh yang buruk: bahkan setelah Anda mengetahui karakterisasi kombinasional dari planaritas, memberikan algoritme waktu polinomial untuk itu masih sangat tidak berarti. Jadi, izinkan saya mengganti contoh yang lebih baik di sini: bagaimana kalau , katakanlah, "diberi masukan dan ditulis dalam biner, hitung berapa banyak warna yang diperlukan untuk mewarnai peta yang berubah-ubah yang tertanam pada permukaan dengan n lubang." Tidak jelas apriori bahwa ini dapat dihitung sama sekali (atau bahkan terbatas!). Tapi ada rumus yang diketahui memberikan jawabannya, dan begitu Anda tahu rumusnya, itu sepele untuk dihitung dalam waktu polinomial. Sementara itu, "mengurangi menjadi anak di bawah umur / teori Robertson-Seymour" mungkin harus ditambahkan sebagai alasan menyeluruh yang terpisah mengapa sesuatu bisa menjadi dalam P.)

Bagaimanapun, ini secara khusus bukan situasi yang paling menarik minat saya.

(1) Pemrograman dinamis. Masalah dapat dipecahkan dengan cara yang memungkinkan solusi rekursif tanpa ledakan eksponensial - seringkali karena kendala yang harus dipenuhi diatur dalam linear atau urutan sederhana lainnya. "Murni kombinasi"; tidak diperlukan struktur aljabar. Dapat diperdebatkan, jangkauan grafik (dan karenanya 2SAT) adalah kasus khusus.

(2) Matroid. Masalah memiliki struktur matroid, memungkinkan algoritma serakah bekerja. Contoh: cocok, pohon spanning minimum.

(3) Aljabar linier. Masalah dapat direduksi menjadi penyelesaian sistem linier, menghitung determinan, menghitung nilai eigen, dll. Dapat disangkal, sebagian besar masalah yang melibatkan "pembatalan ajaib," termasuk yang dipecahkan oleh formalisme matchgate Valiant, juga berada di bawah payung linear-aljabar.

(4) Convexity. Masalah dapat dinyatakan sebagai semacam optimasi cembung. Pemrograman semidefinite, pemrograman linier, dan permainan zero-sum adalah kasus khusus yang semakin meningkat.

(5) Pengujian identitas polinomial. Masalah dapat direduksi menjadi pengecekan identitas polinomial, sehingga Teorema Dasar Aljabar mengarah ke algoritma acak yang efisien - dan dalam beberapa kasus, seperti primality, bahkan algoritma yang terbukti dapat menentukan.

(6) Rantai Markov Monte Carlo. Masalah dapat direduksi menjadi sampling dari hasil jalan cepat yang bercampur. (Contoh: kira-kira menghitung kecocokan sempurna.)

(7) Algoritma Euclidean. GCD, fraksi lanjutan ...

Lain-lain / Tidak jelas bagaimana mengklasifikasikan: Perkawinan yang stabil, anjak piutang, masalah keanggotaan untuk kelompok permutasi, berbagai masalah lain dalam teori bilangan dan teori kelompok, masalah kisi dimensi rendah ...

Pertanyaan saya adalah: apa hal terpenting yang saya tinggalkan?

Untuk memperjelas:

• Saya menyadari bahwa tidak ada daftar yang mungkin lengkap: berapapun jumlah alasan yang Anda berikan, seseorang akan dapat menemukan masalah eksotis yang ada di P tetapi tidak dengan alasan tersebut. Sebagian karena alasan itu, saya lebih tertarik pada ide-ide yang menempatkan banyak masalah berbeda, yang tampaknya tidak terkait dalam P atau BPP, daripada ide-ide yang hanya bekerja untuk satu masalah.

• Saya juga menyadari bahwa itu subjektif bagaimana membagi sesuatu. Misalnya, haruskah matroid hanya menjadi kasus khusus pemrograman dinamis? Apakah solvabilitas dengan pencarian mendalam-pertama cukup penting untuk alasannya sendiri, terpisah dari pemrograman dinamis? Juga, sering kali masalah yang sama dapat di P karena beberapa alasan, tergantung pada bagaimana Anda melihatnya: misalnya, menemukan nilai eigen utama dalam P karena aljabar linier, tetapi juga karena itu adalah masalah optimasi cembung.

Singkatnya, saya tidak berharap untuk "teorema klasifikasi" - hanya untuk daftar yang berguna mencerminkan apa yang saat ini kita ketahui tentang algoritma yang efisien. Dan itulah mengapa yang paling menarik minat saya adalah teknik untuk menempatkan hal-hal di P atau BPP yang memiliki penerapan luas tetapi itu tidak masuk dalam daftar di atas - atau ide-ide lain untuk meningkatkan upaya mentah saya pertama kali untuk membuat yang baik pada kesombongan saya ke ahli fisika.

Beberapa kelas grafik memungkinkan algoritma waktu polinomial untuk masalah yang NP-keras untuk kelas semua grafik. Misalnya, untuk grafik yang sempurna, orang dapat menemukan set independen terbesar dalam waktu polinomial (terima kasih kepada vzn dalam komentar untuk menyinggahi ingatan saya). Melalui konstruksi produk, ini juga memungkinkan penjelasan terpadu untuk beberapa CSP yang tampaknya sangat berbeda untuk dapat ditelusur (seperti yang memiliki struktur pohon yang biasanya diselesaikan dengan dekomposisi hierarkis, dan kendala All-Different yang biasanya diselesaikan dengan pencocokan sempurna).

Dapat diperdebatkan bahwa grafik sempurna adalah "mudah" karena mereka memungkinkan formulasi pemrograman semidefinit yang bagus dari masalah yang bersangkutan (dan karena itu termasuk dalam aljabar linier dan / atau cembung). Namun, saya tidak yakin sepenuhnya menangkap apa yang sedang terjadi.

• András Z. Salamon dan Peter G. Jeavons, Kendala sempurna dapat ditelusuri , CP 2008, LNCS 5202, 524–528. doi: 10.1007 / 978-3-540-85958-1_35

• Meinolf Sellmann, The Polytope Masalah Kepuasan Kendala Biner Terstruktur Pohon , CPAIOR 2008, LNCS 5015, 367-371. doi: 10.1007 / 978-3-540-68155-7_39

Seperti dicatat oleh Gil Kalai, sifat-sifat grafik yang membentuk kelas minor-tertutup dapat didefinisikan oleh sekelompok terbatas anak di bawah umur terlarang (ini adalah teorema Robertson-Seymour ). Hasil lain dari Robertson dan Seymour adalah bahwa pengujian untuk keberadaan anak di bawah umur dapat dilakukan dalam waktu kubik. Bersama-sama ini mengarah ke algoritma polinomial-waktu untuk memutuskan properti yang tertutup kecil.

• Neil Robertson dan PD Seymour, Graph Minors. XIII. Masalah jalur terputus-putus , Journal of Combinatorial Theory, Series B 63 (1) 65-110, 1995. doi: 10.1006 / jctb.1995.1006

Satu masalah dengan properti grafik minor-tertutup adalah bahwa mereka "kecil"; tidak termasuk satu pun minor tidak termasuk banyak grafik. Ini mungkin salah satu alasan Robertson-Seymour berfungsi sebagai dekomposisi struktural: ada beberapa grafik yang tersisa untuk memiliki struktur yang bagus.

• Serguei Norine, Paul Seymour, Robin Thomas, dan Paul Wollan, keluarga tertutup kecil yang tepat adalah kecil , Jurnal Teori Kombinatorial, Seri B 96 (5) 754–757, 2006. doi: 10.1016 / j.jctb.2006.01.006 ( pracetak )

Salah satu upaya untuk melampaui kelas-kelas kecil-tertutup adalah melalui kelas-kelas yang didefinisikan oleh subgraph terlarang atau subgraph yang diinduksi terlarang.

Properti grafik yang didefinisikan oleh himpunan terbatas dari subgraf terlarang atau subgraf yang diinduksi dapat ditentukan dalam waktu polinomial, dengan memeriksa semua kemungkinan subgraf.

Saya menemukan kasus yang sangat menarik untuk menjadi properti grafik herediter di mana set terlarang tidak terbatas . Properti herediter ditutup dengan mengambil substruktur yang diinduksi, atau ekuivalen terdiri dari struktur bebas- , di mana adalah seperangkat substruktur yang diinduksi terlarang, tidak harus terbatas. Untuk kelas- gratis, himpunan tak terbatas tidak mengarah ke algoritma pengenalan dengan cara yang jelas.F F $F$$F$$F$$F$

Juga tidak jelas mengapa untuk beberapa kelas grafik bebas orang harus dapat menemukan set independen terbesar dalam waktu polinomial. Pohon adalah grafik bebas siklus; grafik bipartit adalah grafik bebas siklus aneh; grafik sempurna adalah grafik bebas-lubang (ganjil, aneh-antihole). Dalam setiap kasus ini himpunan terlarang tidak terbatas namun ada algoritma waktu polinomial untuk menemukan set independen terbesar, dan grafik tersebut juga dapat dikenali dalam waktu polinomial.$F$

Sejauh ini hanya ada sebagian kemajuan dalam memahami mengapa beberapa kelas bebas- (dengan tak terbatas) dapat ditentukan dalam waktu polinomial. Kemajuan ini terdiri dari teorema dekomposisi struktural yang mengarah pada algoritma pengenalan polinomial-waktu untuk kelas-kelas tersebut. Grafik sempurna adalah (odd-hole, odd-antihole) -gratis, namun dapat dikenali dalam waktu polinomial oleh algoritma Chudnovsky-Cournéjols-Liu-Seymour-Vušković . (Ini tetap agak berantakan setelah lama dibersihkan.) Ada juga hasil jika adalah himpunan semua siklus genap, atau himpunan semua lubang ganjil, dan kemajuan signifikan telah dibuat pada kasus di mana berisi grafik cakar .F F $F$$F$$F$$F$

• Maria Chudnovsky dan Paul Seymour, Tidak termasuk subgraph yang diinduksi , Survei di Combinatorics 2007, 99–119, Cambridge University Press, ISBN 9780521698238. ( pracetak )

Kasus keturunan berbagi beberapa kesulitan dari kasus anak di bawah umur. Untuk kelas grafik minor-tertutup, biasanya tidak diketahui apa himpunan terbatas dari anak di bawah umur terlarang, meskipun harus terbatas. Untuk kelas grafik bebas, jika himpunan tidak terbatas maka kelasnya mungkin bagus atau mungkin tidak, dan saat ini kami tidak memiliki cara lain selain mencoba memahami struktur dekomposisi grafik bebas.F $F$$F$$F$

Reduksi basis-kisi (algoritma LLL). Ini dasar untuk faktorisasi polinomial integer yang efisien dan beberapa algoritma cryptanalytic yang efisien seperti pemecahan generator linear-kongruensi dan RSA derajat rendah. Dalam beberapa hal Anda dapat melihat algoritma Euclidean sebagai kasus khusus.

Pemrograman integer Lenstra dalam dimensi terbatas, algoritma Lenstra-Lenstra-Lovasz, dan algoritma berikutnya yang terkait - algoritma Barvinok untuk jumlah solusi integer untuk masalah IP dalam dimensi terbatas dan algoritma P-Kannan untuk masalah Frobenius / Sylvester dapat ditambahkan sebagai kategori khusus. Masalah terbuka yang penting di sini adalah menemukan algoritma-P untuk masalah tingkat tinggi di Hierarki Presburger.

Kelas lain dari algoritma P yang layak disebutkan adalah algoritma P yang diberikan pada objek yang terbukti ada dengan bukti acak. Contoh: algoritma untuk aplikasi Lovasz-Local Lemma; versi algoritme hasil perbedaan Spencer; (dengan rasa yang sedikit berbeda) versi algoritmik dari keteraturan Szemeredi keteraturan.

Ada sejumlah besar dan masih berkembang teori tentang kelas masalah kepuasan kendala templat tetap yang memiliki algoritma waktu polinomial. Banyak dari pekerjaan ini membutuhkan penguasaan buku Hobby dan MacKenzie , tetapi untungnya bagi kita yang lebih tertarik pada ilmu komputer daripada aljabar universal, beberapa bagian dari teori ini sekarang telah cukup disederhanakan untuk dapat diakses oleh audiens TCS.

Masing-masing masalah ini dikaitkan dengan seperangkat hubungan , dan dapat dinyatakan sebagai: diberi sumber struktur relasional dan target struktur relasional dengan hubungan dari , apakah ada struktur homomorfisme struktur relasional dari ke ?S T Γ S T$\Gamma$$S$$T$$\Gamma$$S$$T$

Contoh NP-hard adalah ketika adalah himpunan yang berisi relasi yang dibentuk oleh tepi berarah bolak-balik dari grafik lengkap dengan setidaknya simpul: ini mengekspresikan Grafik -Colouring. Contoh dalam P adalah ketika setiap relasi dalam berisi tuple : dalam hal ini memetakan setiap elemen ke di adalah solusi (sepele).k ≥ 3 k Γ ( 0 , 0 , … , 0 ) S 0 $\Gamma$$k \ge 3$$k$$\Gamma$$(0,0,\dots,0)$$S$$0$$T$

Dipercayai bahwa ada dikotomi untuk masalah-masalah ini, yang dapat dinyatakan secara kasar sebagai: masalah untuk ada di P tepat ketika aljabar yang terkait dengan memiliki istilah Taylor (perhatikan bahwa saya mengabaikan beberapa kondisi penting untuk demi eksposisi). Ini memperluas teorema Dikotomi Schaefer ke kasus di mana himpunan yang digunakan untuk membangun hubungan dalam mengandung lebih dari dua elemen tetapi masih terbatas. Dikotomi ini dikenal ditahan untuk kasus penting di mana hubungan di yang konservatifΓ Γ $\Gamma$$\Gamma$$\Gamma$$\Gamma$; ini berarti dalam praktiknya bahwa kelas masalah mengandung semua subproblem yang lebih sederhana dan berturut-turut dianggap oleh pemecah kendala, sehingga proses penyelesaian kendala menghindari menghasilkan instance perantara yang "keras" sambil memecahkan masalah "mudah".

Dalam satu kasus penting yang termasuk dalam P, metode yang mirip dengan eliminasi Gaussian dapat diterapkan. Ini berfungsi jika diperoleh dari sistem persamaan linear atas bidang terbatas. Lebih mengejutkan lagi, ini juga berfungsi untuk sejumlah masalah yang pada pandangan pertama tidak ada hubungannya dengan aljabar linier. Mereka semua bergantung pada hubungan di yang ditutup di bawah polimorfisme "baik". Ini adalah fungsi yang diterapkan secara komponen untuk koleksi tupel dari relasi untuk menghasilkan tupel lain, yang kemudian harus dalam relasi. Contoh dari polimorfisme yang "baik" adalah istilah Taylor atau siklik.$\Gamma$$\Gamma$

Hasil hingga saat ini tampaknya menunjukkan bahwa harus ada semacam transformasi powering umum dari ruang keadaan keterjangkauan yang mendasarinya yang dapat mengubah masalah tersebut menjadi masalah dengan tuple konstan di setiap relasi, seperti contoh di atas. (Ini adalah interpretasi pribadi saya dari penelitian yang sedang berlangsung dan mungkin benar-benar salah , tergantung pada bagaimana pencarian yang sedang berlangsung untuk algoritma aljabar dengan istilah siklik keluar, jadi saya berhak untuk mengakui kesalahan ini.) Diketahui bahwa ketika tidak ada 't seperti transformasi maka masalahnya adalah NP-lengkap. Perbatasan dugaan dikotomi saat ini melibatkan penutupan celah ini; lihat daftar masalah terbuka dari Workshop 2011 tentang Aljabar dan CSP .

Dalam kedua kasus, ini mungkin layak masuk dalam daftar Scott.

Kelas kedua di PTIME memungkinkan teknik konsistensi lokal diterapkan untuk memangkas kemungkinan solusi, sampai salah satu solusi ditemukan atau tidak ada solusi yang mungkin. Ini pada dasarnya adalah versi canggih cara kebanyakan orang memecahkan masalah Sudoku. Saya tidak berpikir alasan ini saat ini fitur dalam daftar Scott.

Sangat menarik bahwa algoritma PTIME Libor Barto untuk kasus konservatif dengan adanya istilah siklik adalah tidak konstruktif: jika ada subalgebra penyerap maka ada algoritma, tetapi tidak ada cara yang diketahui untuk memutuskan apakah suatu set adalah subalgebra penyerap dari sebuah aljabar. Bandingkan ini dengan pengaturan Robertson-Seymour, di mana ada algoritme tetapi ia bergantung pada mengetahui himpunan terbatas anak di bawah umur yang terlarang, namun tidak ada cara yang diketahui bagaimana memutuskan apakah seperangkat grafik terbatas adalah daftar anak di bawah umur terlarang dari kelas grafik . Algoritma Barto bergantung pada mengetahui subuniverses yang menyerap dari semua himpunan bagian dari aljabar yang terkait dengan , dan dari sifat eksistensial dari algoritma yang katanya "Aku menyukainya" ...$\Gamma$

Akhirnya, ada juga banyak pekerjaan menarik yang diprakarsai oleh Manuel Bodirsky untuk kasus domain tak terbatas. Beberapa algoritma terlihat sangat aneh dan pada akhirnya mungkin mengarah pada lebih banyak entri dalam daftar Scott.

Saya melihat Chandra menyinggung itu, tetapi saya pikir struktur relaksasi LP (misalnya karena unimodularitas total) adalah bentuk "struktur" yang menyebar yang mengarah ke polinomialitas. Ini menyumbang kelas besar algoritma waktu poli. Jika seseorang termasuk masalah janji, itu menyumbang kelas besar algoritma perkiraan juga. Kelas alasan yang paling sering dijumpai yang tidak mengikuti dari piringan hitam dan / atau SDP adalah eliminasi Gaussian dan pemrograman dinamis. Tentu saja ada yang lain seperti algoritma holografik yang tidak memiliki penjelasan sederhana.