Algorytmy czasu wielomianowego z dużym wykładnikiem / stałą

Czy znasz rozsądne algorytmy działające w czasie wielomianowym w (Długość wejściowa + Długość wyjściowa), ale których asymptotyczny czas działania w tej samej mierze ma naprawdę ogromny wykładnik / stałą (przynajmniej tam, gdzie jest udowodniona górna granica czasu działania taka droga)?

Algorytmy oparte na lemacie regularności są dobrym przykładem algorytmów wielomianowych ze straszliwymi stałymi (zarówno w wykładniku wykładniczym, jak i jako wiodące współczynniki).

Lemat o regularności Szemeredi mówi ci, że na dowolnym wykresie wierzchołków możesz podzielić wierzchołki na zestawy, w których krawędzie między parami zbiorów są „pseudolosowe” (tj. Gęstości wystarczająco dużych podzbiorów wyglądają jak gęstości na losowym wykresie) . Jest to struktura, z którą bardzo miło jest pracować, w związku z czym istnieją algorytmy korzystające z partycji. Chodzi o to, że liczba zestawów w partycji jest wykładniczą wieżą w parametrze pseudolosowości (patrz tutaj: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma ).$n$

Niektóre linki do algorytmów opartych na lemacie regularności, patrz np .: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf

Wiadomości z SODA 2013 : problem Max-Bisection można zbliżyć do współczynnika 0,8776 w czasie .$O(n^{10^{100}})$

Oto dwa zrzuty ekranu z podejścia opartego na energii do rozwijania powiązań autorstwa Jasona H. Cantarelli, Erika D. Demaine, Hayley N. Iben, Jamesa F. O'Briena, SOCG 2004:

Oto najnowszy wynik z papierowej łamigłówki FUN 2012 autorstwa Erika D. Demaine'a, Martina L. Demaine'a, Yaira N. Minsky'ego, Josepha SB Mitchella, Ronalda L. Rivesta i Mihai Patrascu.

Pokazujemy, jak zawiesić zdjęcie, owijając linę wokół n gwoździ, tworząc wielomianową liczbę skrętów, tak że zdjęcie spada, gdy jakikolwiek z n gwoździ zostanie usunięty, a zdjęcie pozostaje zawieszone, gdy zostanie usuniętych mniej niż k gwoździ.

Nie daj się zwieść „wielomianowi” ... okazuje się, że to .$O(n^{43737})$

Istnieje klasa problemów, których rozwiązania są trudne do obliczenia, ale zbliżać je do dowolnej dokładności jest łatwe , w tym sensie, że istnieje wielomian czasie algorytmy, które mogą zbliżyć się do rozwiązania w ciągu dla dowolnej stałej ε> 0. Istnieje jednak pewien haczyk: czas działania aproksymatorów może bardzo źle zależeć od 1 / ,, np. Być O ( n 1 / ϵ ) .$(1+\epsilon)$$1/\epsilon$$O(n^{1/\epsilon})$

Zobacz więcej informacji tutaj: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme .

Chociaż czas działania takich algorytmów został następnie poprawiony, pierwotny algorytm próbkowania punktu z wypukłego ciała miał czas pracy .$\tilde{O}(n^{19})$

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

Jeśli jest tabelaryczną modalną lub superintuicyjną logiką, wówczas rozszerzone systemy Frege i podstawienia Frege proof dla L są wielomianowo równoważne, a wielomianowo wiernie interpretowalne w klasycznej EF (to jest twierdzenie 5.10 w moim artykule ). Wykładnik c symulacji wielomianowych nie jest wyraźnie określony w Twierdzeniu 5.10, ale dowód indukcyjny twierdzenia daje c = 2 O ( | F | ) , gdzie F jest skończoną ramką Kripkego, która generuje L , więc może być tak ogromna jak chcesz w zależności od logiki. (Gorzej w twierdzeniu 5.20.)$L$$L$$c$$c=2^{O(|F|)}$$F$$L$

Obecnie najbardziej znany algorytm rozpoznawania grafów map (uogólnienie grafów płaskich) działa . Thorup, Mapa wykresów w czasie wielomianowym.$n^{120}$

Obliczenie równowagi na rynku Arrow-Debreu wymaga obliczeń maksymalnego przepływu , gdzie U jest maksymalną użytecznością. Duan, Mehlhorn, kombinatoryczny algorytm wielomianowy dla rynku liniowego Arrow-Debreu.$O(n^6\log(nU))$$U$

Problem przemijalności piaskowca

Rozważ następujący proces. Weź grubą płytkę i upuść na nią cząsteczki piasku po jednym ziarnie na raz. Stos stopniowo narasta, a następnie duża część piasku zsuwa się z krawędzi płytki. Jeśli nadal będziemy dodawać cząsteczki piasku, po pewnym czasie konfiguracja hałdy zostanie powtórzona. Następnie konfiguracja staje się cykliczna, tzn. Ciągle powraca do stanu widocznego wcześniej.

Rozważ następujący model powyższego procesu. Modeluj kafelek jako siatkę . Cząsteczki piasku są upuszczane na wierzchołki tej siatki. Jeśli liczba cząstek w wierzchołku przekracza swój stopień, wówczas wierzchołek zapada się, a cząstki w nim przemieszczają się do sąsiednich wierzchołków (w sposób kaskadowy). Cząstka piasku, która osiąga graniczny wierzchołek, znika w zlewie (`` spada ''). Jest to znane jako Abelowy model piaskowca .$n \times n$

Problem: Ile czasu zajmuje konfiguracja, aby stała się powtarzalna pod względem , przy założeniu najgorszego algorytmu upuszczania cząstek piasku?$n$

W SODA '07 László Babai i Igor Gorodezky udowodnili, że tym razem są wielomianowo ograniczeni, ale ..

W SODA '12 Ayush Choure i Sundar Vishwanathan poprawili to ograniczenie do .$O(n^7)$

Ta odpowiedź wyglądałaby nieco lepiej, gdyby nie ich ulepszenie :)

Problem „wypukłej czaszki” polega na znalezieniu wypukłego wielokąta o maksymalnym polu wewnątrz danego prostego wielokąta. Najszybszy algorytm znany z tego problemu działa w czasie [Chang and Yap, DCG 1986].$O(n^7)$

Rozwiązanie Annihilation Games (Fraenkel i Yesha) ma złożoność .$O(n^6)$

Istnieje kilka niekonstruktywnych algorytmów, w szczególności twierdzenie Fellowsa i Langstona oraz Courcelle'a .

Ponadto algorytm liniowo-czasowy Bodlaendera dla szerokości drzewa i twierdzenie Courcelle'a są niezwykle niepraktyczne.

$G$$O(n^3)$$H$$n$$G$$G$

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

$O(n^{11})$

W prostokącie wielokąta, część 2: Minimalna liczba prostokątów tłuszczu , praktyczna modyfikacja problemu podziału prostokąta motywowana obawami w VLSI:

$P$$\delta$$P$$\delta$

$O(n^{42})$

$O(2^n)$$n$$n \choose 1$$n \choose 2$$n \choose 3$$O(n^c)$$c$$n \choose c$$c$$\mathsf{P \neq NP}$

[1] Pytania dotyczące sztywności macierzy obliczeniowej

$c$$O(n^c)$$n \choose c$$\mathsf{P \neq NP}$