Masalah yang terasa eksponensial tetapi P

12

Saya mencoba membuat daftar algoritma / masalah yang "sangat berguna", seperti dalam, memecahkan masalah yang 'tampak' sangat eksponensial di alam, tetapi memiliki beberapa algoritma yang sangat pintar yang akhirnya menyelesaikannya. Contoh yang saya maksud:

  • Linear Programming (Algoritma simpleks adalah waktu eksponensial; butuh waktu lama untuk menemukan solusi waktu polinomial!)
  • Lebih umum, Pemrograman Semidefinite
  • Pengujian primality
  • 2-SAT dan HORNSAT
  • Penentu komputasi (jika ini kedengarannya tidak sulit, pertimbangkan yang permanen)
  • Menemukan pasangan yang sempurna
  • Berbagai masalah teori kelompok keras yang dapat diselesaikan dengan menggunakan Klasifikasi Kelompok Sederhana Hingga
  • Berbagai masalah grafik keras yang dapat diselesaikan dengan menggunakan karakterisasi Forbidden Minor yang rumit (dapat ditanamkan pada permukaan yang sewenang-wenang; pembatas jalur lebar dan lebar cabang; grafik yang dapat direduksi Delta-Wye)
  • Komputasi eksponensial dalam grup terikat (mis. Menghitung dalam \ log b langkah, seperti yang dilakukan dengan kuadrat ulang)log babmodklog⁡b
  • Komputasi mengandalkan algoritma LLL. (Sebagai kasus khusus: Algoritma Euclidean. Sebagai kasus yang lebih umum: Algoritma PSLQ atau HJLS.)
  • Kendala masalah tanpa istilah Taylor (?). Saya akui saya tidak sepenuhnya memahami hal ini, tetapi sepertinya ini mungkin merangkum kasus 2-SAT / HORNSAT di atas, dan aljabar linear apa pun di bidang terbatas. Lihat di sini untuk posting yang lebih panjang
  • Masalah dapat dihitung melalui pengurangan holografik .

Sebagai penyebutan terhormat, saya juga akan menyebutkan Graph Isomorphism, karena itu masih sangat mudah ( ), dan setara dengan begitu banyak masalah isomorfisma lainnya:nlog2⁡n

  • Digraphs / multigraphs / hypergraphs (semacam masalah 'sulit')
  • Automata / CFG terbatas

Jelas ada sejumlah kesulitan dalam hal ini, tetapi semua meninggalkan setidaknya beberapa orang dengan perasaan 'terkejut' dalam arti bahwa masalahnya bisa terdengar sulit tetapi ternyata bisa diselesaikan. LP mungkin terdengar relatif mudah, tetapi orang butuh waktu cukup lama untuk membangun solusi aktual. Mengkuadratkan atau memecahkan 2-SAT berulang adalah sesuatu yang mungkin dapat dilakukan oleh seorang sarjana, tetapi jika Anda hanya belajar tentang masalah NP-Complete tanpa melihat HORNSAT, itu mungkin terdengar seperti kandidat alami untuk NP-Completeness. Memecahkan CFSG atau memiliki cara polinomial untuk memeriksa reducabilitas Delta-Wye bukanlah prestasi yang berarti.

Saya harap ini masuk akal; jelas ada banyak atribut subjektif di sini, tetapi saya ingin tahu apa yang orang lain temukan sebagai solusi efisien untuk masalah yang "jelas sulit".

complexity-theory polynomial-time efficiency Alex Meiburg
sumber
Sebagai motivasi untuk pertanyaan ini (karena seorang teman juga bertanya): Kami sering berbicara tentang betapa pentingnya untuk mengajar siswa tentang NP-Completeness dan Undecidability, karena ini membantu mereka mengenali kapan masalah akan Terlalu Keras dan mereka harus menghindarinya. Daftar ini akan menjadi 'masalah Anda mungkin salah untuk NP-Lengkap tetapi Anda benar-benar dapat melakukannya'. Bukannya saya berharap banyak siswa untuk penuh di bawah kesan bahwa determinan tidak dapat dihitung - seperti halnya mereka kemungkinan tidak akan menemukan 3SAT di alam liar - tetapi mereka harus mengenali masalah lain yang setara
Alex Meiburg
1
Saya menduga ini terlalu luas untuk menjadi tempat yang cocok untuk situs kami. Meminta daftar lengkap tentang sesuatu tidak terdengar seperti jenis pertanyaan yang bekerja dengan baik di sini. "Aku penasaran mendengar apa yang orang lain temukan ..." terdengar seperti pertanyaan yang tidak cocok di sini; lihat pusat bantuan kami .
DW
1
Saya mengerti, saya mencoba untuk mengakui subjektivitas dalam pertanyaan ini, tetapi saya pikir pertanyaan ini sebagian besar adalah sesuatu yang orang akan sepakati dan pelajari dari diskusi yang produktif. Untuk pertanyaan yang memiliki nada yang mungkin saya tuju (walaupun saya tahu situs lain), lihat cstheory.stackexchange.com/questions/20930/… atau cstheory.stackexchange.com/questions/11119/… ?
Alex Meiburg
Juga, sama sekali tidak jelas apa yang "terasa" eksponensial kepada siapa.
Raphael

Jawaban:

2

Bagi saya salah satu algoritma yang paling efisien adalah algoritma Blossom V yang menemukan pencocokan sempurna berat maksimum dalam grafik umum:

https://en.m.wikipedia.org/wiki/Blossom_algorithm

Dmitry Kamenetsky
sumber
1
Ini adalah contoh yang bagus! Tidak pernah benar-benar memikirkannya atau membutuhkannya, saya pikir saya mendapat kesan bahwa pencocokan maksimal pada grafik arbitrer adalah NP-hard. :)
Alex Meiburg
1

Bagi saya semua klasik dan algoritma yang lebih efisien baru-baru ini untuk memverifikasi atau menemukan pohon spanning minimum (MST) dari graf berbobot tepi yang terhubung adalah kandidat yang baik. Banyak dari algoritma ini terdaftar di wikipedia .

Pada pandangan pertama, masalah ini seperti masalah salesman keliling, salah satu dari beberapa masalah NP-hard yang paling terkenal. Yang paling menakjubkan, ada algoritma linier untuk memverifikasi MST dan banyak algoritma linier dekat untuk menemukan MST! Bahkan, salah satu masalah terbuka yang paling terkenal dalam algoritma adalah apakah ada algoritma linear deterministik untuk menemukan MST dalam grafik umum. Ternyata ada matematika kaya dan struktur grafik dan properti serta banyak aplikasi praktis yang terkait dengan MST, menjadikannya salah satu topik yang lebih menyenangkan dan diperluas dalam kursus ilmu komputer. Untuk pengantar komprehensif yang sedikit usang tetapi sangat ditulis dengan baik, silakan lihat tutorial oleh Jason Eisner .

John L.
sumber