Algoritma polinomial-waktu dengan eksponen / konstanta besar

Apakah Anda tahu algoritma masuk akal yang berjalan dalam waktu polinomial dalam (Panjang input + Panjang output), tetapi yang menjalankan waktu asimtotik dalam ukuran yang sama memiliki eksponen / konstanta yang sangat besar (setidaknya, di mana batas atas terbukti pada waktu berjalan adalah dalam sedemikian rupa)?

Algoritma berdasarkan lemma keteraturan adalah contoh yang baik untuk algoritma polinomial-waktu dengan konstanta yang mengerikan (baik dalam eksponen atau sebagai koefisien terkemuka).

Lemma keteraturan Szemeredi memberi tahu Anda bahwa dalam grafik apa pun pada simpul Anda dapat mempartisi simpul ke dalam set di mana tepi antara pasangan set "pseudo-acak" (yaitu, kepadatan himpunan bagian yang cukup besar terlihat seperti kepadatan dalam grafik acak) . Ini adalah struktur yang sangat bagus untuk dikerjakan, dan sebagai konsekuensinya ada algoritma yang menggunakan partisi. Tangkapannya adalah bahwa jumlah set dalam partisi adalah menara eksponensial dalam parameter pseudo-randomness (Lihat di sini: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma ).$n$

Untuk beberapa tautan ke algoritma yang mengandalkan lemma keteraturan, lihat, misalnya: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf

Berita dari SODA 2013 : Masalah Max-Bisection diperkirakan sekitar dalam faktor 0,8776 di sekitar waktu waktu.$O(n^{10^{100}})$

Berikut adalah dua tangkapan layar dari Pendekatan Berbasis Energi ke Linkage Unfolding oleh Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, SOCG 2004:

Berikut adalah hasil terbaru dari makalah FUN 2012 Picture-Hanging Puzzles oleh Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph SB Mitchell, Ronald L. Rivest dan Mihai Patrascu.

Kami menunjukkan cara menggantung gambar dengan melilitkan tali di sekitar paku, membuat polinomial dalam jumlah bengkok, sehingga gambar jatuh setiap kali ada k di kuku yang dilepas, dan gambar tetap menggantung ketika lebih sedikit dari k yang dilepas.

Jangan biarkan 'angka polinom' menipu Anda ... ternyata itu .$O(n^{43737})$

Ada kelas masalah, yang solusinya sulit dihitung, tetapi memperkirakannya dengan akurasi apa pun itu mudah , dalam arti ada algoritma waktu polinomial yang dapat memperkirakan solusi ke dalam untuk konstanta ε > 0. Namun, ada tangkapan: waktu menjalankan aproksimator mungkin sangat tergantung pada , misalnya, menjadi .1 / ϵ O ( n 1 / ϵ$(1+\epsilon)$$1/\epsilon$$O(n^{1/\epsilon})$

Lihat info lebih lanjut di sini: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme .

Meskipun run-time untuk algoritma tersebut telah diperbaiki, algoritma asli untuk pengambilan sampel titik dari badan cembung telah menjalankan waktu .$\tilde{O}(n^{19})$

Dyer, Frieze, dan Kannan: http://portal.acm.org/citation.cfm?id=102783

Jika adalah modal tabular atau logika superintuitionistic, maka Frege yang diperluas dan sistem bukti Frege pengganti untuk adalah setara secara polinomi, dan secara polinomi dapat ditafsirkan secara setia dalam EF klasik (ini adalah Teorema 5.10 dalam makalah ini dari saya). Eksponen dari simulasi polinom tidak secara eksplisit dinyatakan dalam Teorema 5.10, tetapi bukti induktif teorema memberikan , di mana adalah kerangka Kripke hingga yang menghasilkan , sehingga ia dapat menjadi sebesar yang Anda inginkan tergantung pada logika. (Itu menjadi lebih buruk dalam Teorema 5.20.)L c c = 2 O ( | F | ) F $L$$L$$c$$c=2^{O(|F|)}$$F$$L$

Algoritma yang paling dikenal saat ini untuk mengenali grafik peta (generalisasi grafik planar) berjalan di . Thorup, Peta grafik dalam waktu polinomial.$n^{120}$

Menghitung ekuilibrium pasar Arrow-Debreu menggunakan perhitungan max-flow , di mana adalah utilitas maksimum. Duan, Mehlhorn, Algoritma Polinomial Kombinatorial untuk Pasar Linear Arrow-Debreu.$O(n^6\log(nU))$$U$

Masalah Tranpensi Sandpile

Pertimbangkan proses berikut. Ambil ubin tebal dan taruh partikel pasir di atasnya satu butir setiap kali. Tumpukan secara bertahap menumpuk dan kemudian sebagian besar pasir terlepas dari tepi ubin. Jika kita terus menambahkan partikel pasir, setelah titik waktu tertentu, konfigurasi tumpukan berulang. Setelah itu, konfigurasi menjadi berulang, yaitu terus meninjau kembali keadaan yang terlihat sebelumnya.

Pertimbangkan model berikut untuk proses di atas. Modelkan ubin sebagai kisi . Partikel pasir dijatuhkan pada simpul dari kisi ini. Jika jumlah partikel pada suatu vertex melebihi derajatnya, maka verteks tersebut akan runtuh dan partikel-partikel di dalamnya akan berpindah ke verteks yang berdekatan (dengan cara cascading). Sebuah partikel pasir yang mencapai titik batas menghilang ke wastafel (`jatuh '). Ini dikenal sebagai Abelian Sandpile Model .$n \times n$

Masalah: Berapa lama waktu yang diperlukan untuk konfigurasi menjadi berulang dalam hal , dengan asumsi algoritma terburuk untuk menjatuhkan partikel pasir?$n$

Dalam SODA '07 , László Babai dan Igor Gorodezky membuktikan kali ini terikat secara polinomi tetapi ..

Dalam SODA '12 , Ayush Choure dan Sundar Vishwanathan meningkatkan ikatan ini menjadi .$O(n^7)$

Jawaban ini akan terlihat sedikit lebih baik jika bukan karena peningkatan mereka :)

Masalah "tengkorak cembung" adalah untuk menemukan poligon cembung luas maksimum di dalam poligon sederhana yang diberikan. Algoritma tercepat yang dikenal untuk masalah ini berjalan dalam waktu [Chang dan Yap, DCG 1986].$O(n^7)$

Solusi dari Annihilation Games (Fraenkel dan Yesha) memiliki kompleksitas .$O(n^6)$

Ada beberapa algoritma yang tidak konstruktif, terutama teorema Fellows dan Langston dan Courcelle .

Juga, algoritma linear-waktu Bodlaender ini untuk pohon-lebar dan teorema Courcelle ini terkenal tidak praktis.

Teorema Robertson-Seymour alias Graph Minor Theorem menetapkan antara lain bahwa untuk setiap grafik , ada algoritma yang menentukan apakah grafik sewenang-wenang (ukuran ) memiliki sebagai minor. Buktinya nonkonstruktif dan konstanta multiplikasi (saya pikir tidak seragam) mungkin sangat besar sehingga tidak ada rumus untuk itu yang dapat dituliskan secara eksplisit (misalnya sebagai fungsi rekursif primitif pada ).$G$$O(n^3)$$H$$n$$G$$G$

http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition

Dalam makalah ICALP 2014 mereka , Andreas Björklund dan Thore Husfeldt memberikan algoritma polinomial pertama (acak) yang menghitung 2 jalur terputus-putus dengan panjang total minimum (jumlah dari dua jalur panjang) antara dua pasang simpul yang diberikan. Waktu berjalan adalah dalam .$O(n^{11})$

Dalam rectangulation Polygon, bagian 2: Jumlah minimum dari persegi panjang lemak , modifikasi praktis dari masalah partisi persegi panjang yang dimotivasi oleh keprihatinan dalam VLSI disajikan:

Lemak Rectangle Optimasi Masalah: Diberi poligon ortogonal , memaksimalkan terpendek sisi atas semua rectangulations dari . Di antara partisi dengan sama , pilih partisi dengan jumlah persegi paling sedikit.$P$$\delta$$P$$\delta$

Sampai saat ini, hanya algoritma teoretis yang ada, dengan waktu berjalan . (Itu bukan kesalahan ketik, dan diperoleh melalui solusi pemrograman dinamis "alami" untuk masalah yang dinyatakan di sana.)$O(n^{42})$

menghitung kekakuan matriks [1] melalui brute force / naif / enumerasi tampaknya membutuhkan waktu untuk matriks ukuran elemen. ini dapat dilihat sebagai batas konvergen urutan perkiraan yang semakin akurat yang mengambil langkah , , , .... dengan kata lain masing-masing perkiraan dalam P-waktu untuk setiap eksponen sewenang-wenang (yaitu langkah). algoritma naif memilih apa saja$O(2^n)$$n$$n \choose 1$$n \choose 2$$n \choose 3$$O(n^c)$$c$$n \choose c$$c$elemen matriks untuk diubah dan diuji untuk pengurangan dimensi yang dihasilkan. ini tidak sepenuhnya mengejutkan mengingat telah dikaitkan dengan rangkaian komputasi batas bawah. ini mengikuti pola di mana banyak algoritme memiliki solusi P-time untuk beberapa parameter tetapi bukti solid dari batas bawah kemungkinan akan menyiratkan atau sesuatu yang lebih kuat.$\mathsf{P \neq NP}$

[1] Pertanyaan tentang kekakuan matriks komputasi

anehnya salah satu jawaban yang paling jelas belum diposting. menemukan klik ukuran (tepi atau simpul) tampaknya membutuhkan waktu oleh algoritma naive / brute force yang menyebutkan semua kemungkinan. atau lebih tepatnya proporsional dengan langkah . (Anehnya, fakta dasar ini tampaknya jarang ditunjukkan dalam literatur.) Namun bukti yang kuat akan menyiratkan . jadi pertanyaan ini terkait dengan dugaan terbuka terkenal, hampir setara dengan itu. masalah tipe NP lainnya dapat diparameterisasi dengan cara ini.$c$$O(n^c)$$n \choose c$$\mathsf{P \neq NP}$