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

59

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)?

Joris
źródło
3
Zobacz mathoverflow.net/questions/65412 : „Najgorszy znany algorytm w kategoriach big-O lub dokładniej big-Theta”. Wysłałem tam odpowiedź.
Joseph O'Rourke
4
Istnieje algorytm LOGSPACE Reingolda dla łączności (patrz pytanie dotyczące jego złożoności czasowej ), ale wątpię, czy jest sensowny w tym sensie, że masz na myśli tutaj ...
Janne H. Korhonen
1
@Joseph ORourke: Mam teraz na biurku papier „gruby prostokąt”!
Aaron Sterling
3
Chociaż n42 był prawidłowym obliczeniem (programowanie dynamiczne go podkręca), zawarłem go w wersji konferencyjnej jako żart , żart usunięty z wersji dziennika.
Joseph O'Rourke
9
Rozpoznawanie idealnych wykresów odbywa się w O(|V.(sol)|9) i wydaje się, że konieczny jest przełom, aby to poprawić.
András Salamon

Odpowiedzi:

39

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

Dana Moshkovitz
źródło
2
Słuszna uwaga! Chociaż nie jestem świadomy problemu obliczeniowego, w którym istnieje odpowiednia dolna granica wieży wykładniczej. Gowers okazał się tak dolną granicą dla samego lematu regularności, ale nie znam problemu obliczeniowego, w którym ma on zastosowanie.
arnab
3
Uważam, że algorytmy flokowania opisane przez Chazelle w tym artykule ( arxiv.org/abs/0905.4241 ) mają optymalną (tj. Mają dolne granice) zbieżność, która jest wieżą dwójki
Suresh Venkat
W niedawnym artykule ( eccc.hpi-web.de/report/2014/018 ) pokazuję kilka innych algorytmów wykorzystujących (arytmetyczną) lemat regularności, które mają ogromne stałe ukryte przez notację O ().
arnab
55

Wiadomości z SODA 2013 : problem Max-Bisection można zbliżyć do współczynnika 0,8776 w czasie .O(n10100)

Jagadish
źródło
54

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:

Następstwo 1. Liczba kroków w naszym algorytmie wynosi najwyżej 1752484608000 n ^ {79} L ^ {25} / D ^ {26} (\ Theta_0) $

Następstwo 2. Liczba kroków w naszym algorytmie wynosi najwyżej 117607251220365312000 n ^ {79} (\ ell _ {\ max} / d _ {\ min} (\ Theta_0)) ^ {26} $]

Jeffε
źródło
12
Stała jest znacznie bardziej imponująca niż moc :)n
Suresh Venkat
11
To jest algorytm z dużym wykładnikiem ORAZ ogromną stałą ...
Hsien-Chih Chang 張顯 之
5
Te same granice są prawdziwe dla Bubblesort.
Raphael,
1
Jak ścisłe są te granice?
Maks.
34

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(n43737)

Jagadish
źródło
15
To (!!)(618)# bramki w sieci sortującej AKS
Jeffε 11.04. O
23

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+ϵ)1/ϵO(n1/ϵ)

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

Sadeq Dousti
źródło
17

Chociaż czas działania takich algorytmów został następnie poprawiony, pierwotny algorytm próbkowania punktu z wypukłego ciała miał czas pracy .O~(n19)

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

Aaron Roth
źródło
16

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.dodo=2)O(|fa|)faL.

Emil Jeřábek
źródło
16

Obecnie najbardziej znany algorytm rozpoznawania grafów map (uogólnienie grafów płaskich) działa . Thorup, Mapa wykresów w czasie wielomianowym.n120

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(n6log(nU))U

rev adrianN
źródło
Dostaję błąd od IEEE, kiedy podążam za twoim linkiem, ale zakładam, że masz na myśli artykuł FOCS'98 Thorupa „Mapuj wykresy w czasie wielomianowym”.
David Eppstein,
1
Mam na myśli ten papier i ładuje się dla mnie dobrze.
adrianN,
pracuje dla mnie z USA
Suresh Venkat,
12

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×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 ..

wprowadź opis zdjęcia tutaj

W SODA '12 Ayush Choure i Sundar Vishwanathan poprawili to ograniczenie do .O(n7)

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

Jagadish
źródło
11

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(n7)

Jeffε
źródło
6

O(n11)

Lamine
źródło
-3

O(2n)n(n1)(n2)(n3)O(nc)c(nc)cPNP

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

vzn
źródło
2
Nie jestem pewien, jak to się różni (na przykład) od próby znalezienia maksymalnej kliki poprzez wyliczenie wszystkich zestawów wielkości k, w celu zwiększenia k. każdy krok jest również czasem p dla ustalonego k.
Suresh Venkat
tak, jest bardzo podobny i przypomina mi hipotezę o izomorfizmie Hartmanisa dla zbiorów NP. nawet jeśli hipoteza o izomorfizmie nie jest prawdziwa (obecny konsensus / konwencjonalna mądrość wydaje się opierać na tym), wydaje się, że zestawy NP mają podobną właściwość, ale może nieco słabszą, co również wymaga wyczerpujących poszukiwań
vzn
-4

doO(ndo)(ndo)P.N.P.

vzn
źródło
2
1. istnieje (prosty) algorytm, który nieznacznie poprawia wykładnik potęgi. 2. jest to znacznie silniejsze stwierdzenie niż P nie równe NP, podobnie jak ETH jest silniejsze niż P nie równe NP. Myślę, że takie algorytmy nie zostały wskazane, ponieważ wydaje się, że OP nie jest zainteresowany wyczerpującymi typami algorytmów wyszukiwania.
Sasho Nikolov
5
dondoO(do)
5
k>2 k2sknsk>0
6
k2knkk2O(k)n
5
2O(n)2O(n)