Masalah keputusan dalam

Apa saja contoh masalah keputusan sulit yang dapat diselesaikan dalam waktu polinomial? Saya mencari masalah dengan algoritma optimal "lambat", atau masalah yang algoritma paling cepat diketahui "lambat".

Berikut ini dua contoh:

• Pengakuan grafik yang sempurna. Dalam makalah FOCS'03 mereka [1] Cornuéjols, Liu dan Vuskovic memberikan algoritma waktu untuk masalah, di mana n adalah jumlah simpul. Saya tidak yakin apakah batasan ini telah diperbaiki, tetapi seperti yang saya pahami, dibutuhkan terobosan untuk mendapatkan algoritma yang lebih cepat. (Para penulis memberikan algoritma waktu O ( n 9 ) dalam versi jurnal [1], lihat di sini ).$O(n^{10})$$n$$O(n^9)$

• Pengakuan grafik peta. Thorup [2] memberikan algoritma yang agak rumit dengan eksponen (sekitar?) . Mungkin ini bahkan telah diperbaiki secara dramatis, tetapi saya tidak memiliki referensi yang baik.$120$

Saya terutama tertarik pada masalah yang memiliki kepentingan praktis, dan mendapatkan algoritma "cepat" (atau bahkan praktis) telah terbuka selama beberapa tahun.

[1] Cornuéjols, Gérard, Xinming Liu, dan Kristina Vuskovic. "Algoritma polinomial untuk mengenali grafik yang sempurna." Yayasan Ilmu Komputer, 2003. Prosiding. Simposium IEEE Tahunan ke-44 pada. IEEE, 2003.

[2] Thorup, Mikkel. "Peta grafik dalam waktu polinomial." Yayasan Ilmu Komputer, 1998. Prosiding. Simposium Tahunan ke 39 pada. IEEE, 1998.

Mungkin masalah berikut cocok dengan contoh Anda:

• (Versi keputusan) Pewarnaan, Klik, Set Stabil, Penutupan dalam grafik yang sempurna. Sejauh ini, satu-satunya algoritma waktu polinomial yang diketahui untuk masalah ini didasarkan pada metode ellipsoid, yang 'lambat' (dan secara numerik tidak stabil).

• Tes AKS-primality dalam waktu . Meskipun banyak perbaikan (saat ini O ( ( log n ) 7.5 ) ), algoritma AKS masih terlalu lambat dalam praktiknya.$O((\log n)^{12})$$O((\log n)^{7.5})$

Ada pertanyaan serupa di atas pada cstheory , dengan banyak contoh mulai dari algoritma "lambat secara realistis tidak realistis" dengan eksponen 6 atau 7 ke atas. Pertanyaan itu juga membahas konstanta besar juga.

Ada satu klasik yang ingin saya tiru karena sepertinya contoh polinomial yang sangat mengerikan (dicuri tanpa malu-malu dari jawaban JeffE):

Akibat wajar 1. Jumlah langkah dalam algoritma kami paling banyak .$1752484608000n^{79}L^{25}/D^{26}(\Theta_0)$

Konsekuensi 2. Jumlah langkah dalam algoritma kami paling banyak $117607251220365312000n^{79}(\ell_{max}/d_{min}(\Theta_0))^{26}.$

Dari: Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, Pendekatan Berbasis Energi untuk Linkage Unfolding , SOCG 2004.