Przykłady problemów, w których algorytmy wykładnicze działają szybciej niż algorytmy wielomianowe dla praktycznych rozmiarów?

Czy znasz jakieś problemy (najlepiej przynajmniej nieco dobrze znane), w których dla praktycznego rozmiaru problemu algorytm wykładniczy działa znacznie szybciej niż najbardziej znany odpowiednik czasu wielomianowego.

Załóżmy na przykład, że problem ma praktyczny rozmiar * i istnieją dwa znane algorytmy: jeden to a drugi to dla pewnej stałej . Oczywiście dla dowolnego algorytm wykładniczy jest preferowany. $n = 100$ $2^n$ $n^c$ $c$ $c > 15$

* Myślę, że praktyczny rozmiar oznaczałby coś powszechnie spotykanego w prawdziwym świecie. Podobnie jak liczba pociągów w sieci.

time-complexity polynomial-time exp-time-algorithms Ozzah
źródło

Myślę, że możesz znaleźć to, czego szukasz w sparametryzowanej literaturze złożoności.

Kaveh

w przypadku algorytmów liniowych istnieje na ogół stały mnożnik, który na ogół nie jest znaczący i często pomijany w złożoności, ale pamiętam, że wydaje się, że bardzo wysoki, to połączenie w miejscu, które było liniowe, ale w najgorszym przypadku coś takiego jak 5000 N ... w tych scenariuszach istnieje duży obszar użytkowy, w którym N ^ 2 będzie mniejszy niż 5000 N, gdzie rozmiar jest mniejszy niż sqrt (5000) oraz mniejsza domena, w której 2 ^ n nadal będzie szybszy, gdzie n jest mniejsze niż log 5000

Grady Player

Odpowiedzi:

Jak na temat algorytmu simpleks do programowania liniowego? W wielu przypadkach jest stosowany w praktyce.

Edytowany dodać: Myślę, że to bardziej „gorszy przypadek wykładniczy algorytm”, który działa skutecznie na praktycznych wystąpień / rozkładów zamiast działa szybciej na praktycznych rozmiarach antagonistycznych przypadkach.

RB
źródło

@diesalbla - zależy to od dokładnego forumaltion. Powołując się na Wikipedię, „w 1972 r. Klee i Minty [32] podali przykład pokazujący, że najgorszym przypadkiem złożoności metody simpleksowej sformułowanej przez Dantzig jest czas wykładniczy”.

Najszybciej algorytm znany na problem identyfikowania czy wykres ma osadzenie bez węzłów wynika Miller i Naimi i wykładniczo w czasie. Teoria Robertsona-Seymoura mówi, że istnieje algorytm dla tego problemu; jednak, aby to zapisać, musielibyśmy znać listę zakazanych nieletnich za osadzanie bez węzłów. Jednak nawet gdybyśmy znali tę listę, algorytm czasu wykładniczego nadal byłby znacznie szybszy w przypadku wykresów o rozsądnych rozmiarach, ponieważ istnieje ponad 250 zakazanych nieletnich, niektóre z nich dość duże. $O(n^3)$

Peter Shor
źródło

W rzeczywistości liczba zakazanych nieletnich nie jest dużym czynnikiem (nawet jeśli było ich 250 milionów), ale część, która mówi, że zajmuje to trochę czasu (nie jestem pewien, czy jest dokładna): , gdzie jest jednym z zakazanych nieletnich jest zły. W praktyce jest to niemożliwe nawet dla | H | = 2.

2^{2^{2^{2^{| H |}}}} \cdot O (n^{3})

$2^{2^{2^{2^{|H|}}}}\cdot O(n^3)$

H

$H$

Saeed,

To nawet autor: sciencedirect.com/science/article/pii/S0095895611000712 , chociaż zbieram zależność odjest nadal okropny.

O (n^{2})

$O(n^2)$

| H |

$|H|$

Emil Jeřábek,

Ponieważ podejmowanie decyzji, czy jest mniejszą liczbą jest problemem NP-zupełnym, można by pomyśleć o zależności odmusi być co najmniej wykładniczy (choć należy pamiętać, że Robertson-Seymour jest nieco gorszy).

H

$H$

G

$G$

| H |

$|H|$

Peter Shor,

-3

Istnieje kilka przykładów wykrywania / testowania pierwotności (nieprobabilistycznych / dokładnych) . Algorytm AKS był pierwszy algorytm pierwszości przeprowadzania badań wykazano, że w P. Nie konkurują w stosunku do niektórych wykładniczej algorytmy czasu „małych” wejścia. Szczegóły są nieco skomplikowane, ponieważ pokazanie tego na ogół wymaga faktycznej implementacji algorytmów, co jest trudnym zadaniem i może zależeć od aspektów specyficznych dla implementacji.

Więcej informacji / szczegółów / odniesień do tego pytania na cs.se:

Kiedy test pierwotności AKS jest rzeczywiście szybszy niż inne testy?

vzn
źródło

O ile mi wiadomo, algorytmy, z którymi AKS konkuruje w praktyce, to albo losowy wielomian (Miller – Rabin, ECPP), albo deterministyczny quasipolynomial (Adleman – Pomerance – Rumeley). Nigdzie w pobliżu czasu wykładniczego.

Emil Jeřábek

Losowa wersja Millera – Rabina, która jest stosowana w praktyce, nie zależy od wilgotności względnej.

Emil Jeřábek

To wszystko jest bardzo prawdziwe, ale nie ma nic wspólnego z pierwotnym pytaniem.

Emil Jeřábek

Tak, wiem to wszystko. I po raz trzeci nie ma to znaczenia. Pytanie dotyczy algorytmów czasu wykładniczego , które w praktyce konkurują ze znanym algorytmem czasu wielomianowego (tutaj AKS). Jedynym algorytmem testowania pierwszeństwa czasu wykładniczego stosowanym w praktyce jest podział próbny, który nie jest konkurencyjny dla liczb o dowolnej niebanalnej wielkości. Algorytmy konkurencyjne stosowane w praktyce są znacznie bardziej wydajne niż wykładnicze, nawet jeśli nie są wielomianowe (ani deterministyczne, ani bezwarunkowe).

Emil Jeřábek

Jabłka i pomarańcze to porównanie AKS (algorytm testowania pierwszorzędności) z GNFS (algorytm faktoringu).

Emil Jeřábek