Masalah yang kontra-intuitif dipecahkan dalam praktik?

Baru-baru ini, saya melalui pengalaman menyenangkan yang menyakitkan dengan menjelaskan secara informal konsep kompleksitas komputasi kepada seorang programmer otodidak berbakat muda, yang tidak pernah mengambil kursus formal dalam algoritma atau kompleksitas sebelumnya. Tidak mengherankan, banyak gagasan yang tampak aneh pada awalnya tetapi masuk akal dengan beberapa contoh (PTIME, tidak bisa ditawar, tidak dapat dikomputasi) , sementara yang lain tampak lebih alami (klasifikasi masalah melalui pengurangan, waktu dan ruang sebagai sumber daya, analisis asimptotik) . Semuanya berjalan dengan baik sampai saya tidak sengaja mengakui bahwa SATdapat dipecahkan secara efisien * dalam praktek ... Dan begitu saja, saya kehilangan mereka. Tidak masalah seberapa meyakinkan saya mencoba untuk memperdebatkan teori, anak itu yakin bahwa itu semua matematika omong kosong buatan yang seharusnya tidak dia pedulikan. Baik...

¯ \ _ (ツ) _ / ¯

Tidak, saya tidak patah hati, saya juga tidak benar-benar peduli dengan apa yang dia pikirkan, itu bukan inti dari pertanyaan ini. Percakapan kami membuat saya memikirkan pertanyaan yang berbeda,

Seberapa banyak saya benar-benar tahu tentang masalah yang secara teoretis tidak dapat dipecahkan (kompleksitas waktu superpolinomial) tetapi secara praktis dapat dipecahkan (melalui heuristik, perkiraan, pemecah SAT, dll.)?

Saya menyadari, tidak banyak. Saya tahu bahwa ada beberapa pemecah SAT yang sangat efisien yang memecahkan masalah besar secara efisien, bahwa Simplex bekerja dengan baik dalam praktiknya, dan mungkin beberapa masalah atau algoritma. Bisakah Anda membantu saya melukis gambar yang lebih lengkap? Masalah yang terkenal atau bahkan kelas masalah apa yang termasuk dalam kategori ini?

TL; DR: Apa masalah yang bisa dipecahkan secara kontra-intuitif dalam praktik? Apakah ada sumber daya (diperbarui) untuk membaca lebih lanjut? Apakah kita memiliki karakterisasi untuk mereka? Dan, akhirnya, sebagai pertanyaan diskusi umum, bukan?

EDIT # 1: Dalam mencoba menjawab pertanyaan diskusi terakhir saya tentang karakterisasi seperti itu , saya diperkenalkan dengan analisis algoritma yang lebih lancar, sebuah konsep yang diperkenalkan oleh Daniel Spielman dan Shang-Hua Teng dalam [1] yang terus-menerus menyisipkan antara kasus terburuk dan analisis algoritma kasus-rata-rata. Ini bukan karakterisasi yang dibahas di atas, tetapi menangkap konsep yang sama, dan menurut saya itu menarik.

[1] Spielman, Daniel A., dan Shang-Hua Teng. "Analisis algoritma yang dihaluskan: Mengapa algoritma simpleks biasanya membutuhkan waktu polinomial." Jurnal ACM (JACM) 51, no. 3 (2004): 385-463.

• Contoh SAT sangat terstruktur (bahkan pada jutaan variabel) sering dapat diselesaikan dalam praktek. Namun, contoh-contoh SAT acak di dekat ambang kepuasan dengan bahkan beberapa ratus variabel masih terbuka (artinya, bahkan dalam praktiknya, jika Anda menghasilkan hal seperti itu, Anda mungkin tidak pernah tahu di masa kehidupan semesta apakah benda yang Anda hasilkan memuaskan atau tidak) menggunakan pemecah SAT saat ini). Anda mungkin tertarik dengan pertanyaan terkait ini dan jawabannya.

• Pencari klik juga sangat bagus "dalam praktik"

  • Sehubungan dengan clique finder, (bagian dari) penjelasan diberikan oleh analisis kasus rata-rata dari algoritma yang dimaksud.

    Lihat https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

• Pemrograman integer dan pemrograman integer-linear campuran (dengan beberapa variabel rasional dan beberapa integer) adalah fokus dari seluruh departemen Riset Operasi, dan seringkali dapat (tetapi tidak selalu) diselesaikan dalam praktik

• Dari apa yang saya pahami, banyak masalah lengkap yang muncul dalam verifikasi seringkali dapat diselesaikan dalam praktik, tetapi "dalam praktiknya" biasanya menyiratkan "pada contoh yang sangat terstruktur". (Sebaliknya, kita masih tidak tahu siapa yang menang untuk contoh kecil dari game Go, yang merupakan masalah lengkap P S P A C E C. )$\mathsf{PSPACE}$$\mathsf{PSPACE}$

• $\mathsf{EXPSPACE}$ lengkap!

• Seperti yang telah ditunjukkan dalam komentar oleh DW, Grafik Isomorfisme dapat dipecahkan dalam praktiknya. Sangat sulit untuk menghentikan perangkat lunak GI modern seperti nauty, bliss, saucy, etc.

The Hindley-Milner tipe digunakan dalam bahasa pemrograman fungsional (Haskell, SML, OCaml). Algoritma tipe-inferensi hampir linier dalam praktiknya dan bekerja dengan sangat baik, tetapi dikenal sebagai DEXPTIME-complete!

Komentar umum: tidak mengherankan bahwa kompleksitas waktu terburuk tidak selalu merupakan ukuran yang sangat baik dari kinerja praktis pada suatu algoritma. Namun, mengatakan bahwa perbedaan antara teori dan praktik membuat teori kompleksitas menjadi tidak berguna sama dengan mengatakan bahwa bilangan asli adalah pemborosan karena kita hanya menggunakan jumlah sangat kecil dari semua bilangan yang tersedia. Seorang filsuf terkenal pernah berkata bahwa "Pengalaman tanpa teori itu buta, tetapi teori tanpa pengalaman hanyalah permainan intelektual."

Lebih banyak contoh, kebanyakan dari bahasa pemrograman:

1. k-CFA (k-Control Flow Analysis) adalah EXPTIME-complete (Van Horn & Mairson 2008), tetapi kompilator yang mengoptimalkan seluruh program seperti MLton tetap melakukannya. Waktu kompilasi panjang, tetapi jarang bencana.
2. Menyelesaikan overloading (dinamis) umumnya NP-lengkap (Palsberg 2012). Tapi kemudian itu jarang menjadi masalah di dunia nyata.
3. $k$
4. Pemecahan SMT umumnya NP-lengkap, tetapi pemecah SMT komersial (seperti Z3 dan CVC4) biasanya cukup performan. Saya tidak bekerja secara langsung dengan pemecah SMT, tetapi saya telah menggunakan Z3 secara tidak langsung dari Liquid Haskell dan Dafny, dan waktu pengecekan tampak OK.
5. Masalah keputusan untuk aritmatika Presburger benar-benar kompleks (Fischer & Rabin 1974), tetapi algoritma keputusan Bill Pugh, tes Omega (Pugh 1991), berjalan secara umum dalam waktu polinomial waktu rendah.

$O$$n$$n$

Referensi:

[1] David Van Horn dan Harry G. Mairson. 2008. Memutuskan kCFA selesai untuk EXPTIME. Dalam Prosiding Konferensi Internasional ACM SIGPLAN ke-13 tentang Pemrograman Fungsional (ICFP '08). ACM, New York, NY, AS, 275-282.

[2] http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf

[3] MJ Fischer dan MO Rabin. 1974. KOMPLEKSITAS SUPER-EXPONENTIAL ARITHMETIC PRESBURGER. Laporan teknikal. Institut Teknologi Massachusetts, Cambridge, MA, AS.

[4] William Pugh. 1991. Tes Omega: algoritma pemrograman integer cepat dan praktis untuk analisis ketergantungan. Dalam Prosiding Konferensi ACM / IEEE 1991 tentang Supercomputing (Supercomputing '91). ACM, New York, NY, AS, 4-13.

pelatihan jaringan saraf menggunakan metode gradient descent juga terbukti sebagai masalah np-hard https://www.cs.utexas.edu/~klivan/crypto-hs.pdf tetapi umumnya dapat dipecahkan dalam praktiknya.