Złożoność czasowa - Time complexity

Wykresy funkcji powszechnie stosowanych w analizie algorytmów , pokazujące liczbę operacji N w funkcji wielkości wejściowej n dla każdej funkcji

W informatyce The złożoność czas jest złożoność obliczeniowa , która opisuje ilość czasu komputerowego potrzebnego do uruchomienia algorytmu . Złożoność czasowa jest powszechnie szacowana poprzez zliczenie liczby operacji elementarnych wykonywanych przez algorytm, przy założeniu, że wykonanie każdej operacji elementarnej zajmuje określoną ilość czasu. Tak więc ilość czasu i liczba operacji elementarnych wykonywanych przez algorytm przyjmuje się za czynnik stały .

Ponieważ czas działania algorytmu może się różnić dla różnych danych wejściowych o tym samym rozmiarze, powszechnie uważa się złożoność czasową najgorszego przypadku , która jest maksymalną ilością czasu wymaganą dla danych wejściowych o danym rozmiarze. Mniej powszechna i zwykle określona wprost jest złożoność przeciętnego przypadku , która jest średnią czasu potrzebnego na dane wejściowe o danej wielkości (ma to sens, ponieważ istnieje tylko skończona liczba możliwych danych wejściowych o danym rozmiarze). W obu przypadkach złożoność czasowa jest ogólnie wyrażana jako funkcja wielkości danych wejściowych. Ponieważ ta funkcja jest generalnie trudna do dokładnego obliczenia, a czas wykonywania małych danych wejściowych zwykle nie jest konsekwencją, zwykle skupia się na zachowaniu złożoności, gdy rozmiar danych wejściowych wzrasta — to jest na asymptotycznym zachowaniu złożoności. Dlatego też złożoność czasu jest powszechnie wyrażane przy użyciu dużego zapisu O , typowo , , , , etc., gdzie n ma wielkość w jednostkach bitów potrzebnych do reprezentacji wejściowych.

Złożoności algorytmiczne są klasyfikowane według typu funkcji występującej w notacji dużego O. Na przykład algorytm o złożoności czasowej jest algorytmem czasu liniowego, a algorytm o złożoności czasowej dla pewnej stałej jest algorytmem czasu wielomianowego .

Tabela typowych złożoności czasowych

Poniższa tabela podsumowuje niektóre klasy powszechnie spotykanych złożoności czasowych. W tabeli poli( x ) = x O (1) , tj. wielomian w  x .

Nazwa Klasa złożoności Czas pracy ( T ( n )) Przykłady czasów działania Przykładowe algorytmy
stały czas O (1) 10 Znalezienie mediany w posortowanej tablicy liczb

Obliczanie (−1) n

odwrotny czas Ackermanna O ( α ( n )) Amortyzowany czas na operację przy użyciu zestawu rozłącznego
iterowany czas logarytmiczny O ( log *  n ) Rozproszona kolorystyka cykli
log-logarytmiczny O (log log n ) Amortyzowany czas na operację przy użyciu ograniczonej kolejki priorytetowej
czas logarytmiczny DLOGTIME O (log  n ) log  n , log ( n 2 ) Wyszukiwanie binarne
czas polilogarytmiczny poli(log  n ) (log  n ) 2
potęga ułamkowa O ( n c ) gdzie 0 < c < 1 n 1/2 , n 2/3 Wyszukiwanie w drzewie kd
czas liniowy O ( n ) n , 2 n + 5 Znajdowanie najmniejszego lub największego elementu w nieposortowanej tablicy , algorytm Kadane , wyszukiwanie liniowe
"n log-star n" czas O ( n log * n ) Seidel „s wielokąt triangulacji algorytm.
czas liniowy O ( n log n ) n log n , log n ! Najszybsze możliwe sortowanie porównawcze ; Szybka transformata Fouriera .
czas quasilinearny n poli(log n )
czas kwadratowy O ( n 2 ) n 2 Sortowanie bąbelkowe ; Sortowanie przez wstawianie ; Splot bezpośredni
czas sześcienny O ( n 3 ) n 3 Mnożenie naiwne dwóch macierzy n × n . Obliczanie korelacji cząstkowej .
czas wielomianowy P 2 O (log n ) = poli( n ) n 2 + n , n 10 algorytm Karmarkara dla programowania liniowego ; Test pierwszości AKS
czas quasi-wielomianowy QP 2 poli(log  n ) n log log n , n log  n Najlepiej znany algorytm aproksymacyjny O (log 2 n ) dla ukierunkowanego problemu drzewa Steinera .
czas podwykładniczy
(pierwsza definicja)
SUBEXP O (2 n ε ) dla wszystkich ε > 0 Zawiera BPP, chyba że EXPTIME (patrz poniżej) równa się MA .
czas podwykładniczy
(druga definicja)
2 o ( n ) 2 n 1/3 Najlepiej znany algorytm do całkowitej faktoryzacji ; dawniej najlepszy algorytm izomorfizmu grafów
czas wykładniczy
(z wykładnikiem liniowym)
mi 2 O ( n ) 1,1 n , 10 n Rozwiązanie problemu komiwojażera za pomocą programowania dynamicznego
czas wykładniczy EXPTIME 2 poli( n ) 2 n , 2 n 2 Rozwiązywanie mnożenia łańcucha macierzy za pomocą wyszukiwania brute-force
czas czynnikowy O ( n !) n ! Rozwiązywanie problemu komiwojażera za pomocą wyszukiwania brute-force
podwójny czas wykładniczy 2-EXPTIME 2 2 poli( n ) 2 2 n Rozstrzyganie prawdziwości danego stwierdzenia w arytmetyce Presburgera

Stały czas

Mówi się, że algorytm jest stałym czasem (zapisanym również jako O (1) czas), jeśli wartość T ( n ) jest ograniczona wartością, która nie zależy od rozmiaru danych wejściowych. Na przykład dostęp do dowolnego pojedynczego elementu w tablicy zajmuje stały czas, ponieważ tylko jedna operacja musi zostać wykonana, aby go zlokalizować. W podobny sposób znalezienie minimalnej wartości w tablicy posortowanej w porządku rosnącym; to jest pierwszy element. Jednak znalezienie minimalnej wartości w nieuporządkowanej tablicy nie jest operacją o stałym czasie, ponieważ konieczne jest skanowanie każdego elementu w tablicy w celu określenia minimalnej wartości. Jest to więc operacja czasu liniowego, przyjmująca czas O ( n ). Jeśli jednak liczba elementów jest znana z góry i nie zmienia się, można powiedzieć, że taki algorytm nadal działa w stałym czasie.

Pomimo nazwy „stały czas”, czas działania nie musi być niezależny od rozmiaru problemu, ale górna granica czasu działania musi być ograniczona niezależnie od rozmiaru problemu. Na przykład, zadanie „wymieniają wartości i B , jeśli to konieczne, aby ≤ b ” nazywana jest stałą czasu mimo, że czas może zależeć od tego, czy jest to już prawdą, że ≤ b . Jednak istnieje pewna stała t taka, że ​​wymagany czas wynosi zawsze co najwyżej t .

Oto kilka przykładów fragmentów kodu, które działają w stałym czasie:

int index = 5;
int item = list[index];
if (condition true) then
    perform some operation that runs in constant time
else
    perform some other operation that runs in constant time
for i = 1 to 100
    for j = 1 to 200
        perform some operation that runs in constant time

Jeśli T ( n ) to O ( dowolna stała wartość ), to jest to równoważne i określone w standardowym zapisie jako T ( n ) to O (1).

Czas logarytmiczny

Algorytm nazywa się czas logarytmicznej przy T ( n ) = O (log n ) . Ponieważ log a  n i log b  n są powiązane stałym mnożnikiem , a taki mnożnik nie ma znaczenia dla klasyfikacji big-O, standardowe użycie algorytmów logarytmicznych to O (log n ) niezależnie od podstawy logarytmu występującego w wyrażenie T .

Algorytmy biorące czas logarytmiczny są często spotykane w operacjach na drzewach binarnych lub podczas wyszukiwania binarnego .

O (log n algorytm) jest za bardzo skuteczny jako stosunek liczby operacji do wielkości wkładu zmniejsza się i zbliża się do zera, gdy n wzrasta. Algorytm, który musi mieć dostęp do wszystkich elementów swojego wejścia, nie może zająć czasu logarytmicznego, ponieważ czas potrzebny na odczytanie danych wejściowych o rozmiarze n jest rzędu n .

Przykład czasu logarytmicznego podaje wyszukiwanie słownikowe. Rozważmy słownik D, który zawiera n wpisów posortowanych w porządku alfabetycznym . Przypuszczamy, że dla 1 ≤ kn można uzyskać dostęp do k- tego wpisu słownika w stałym czasie. Niech D ( k ) oznacza ten k- ty wpis. Zgodnie z tymi hipotezami test sprawdzający, czy słowo w znajduje się w słowniku, można przeprowadzić w czasie logarytmicznym: rozważ , gdzie oznacza funkcję podłogi . Jeśli , to koniec. W przeciwnym razie, jeśli , kontynuuj wyszukiwanie w ten sam sposób w lewej połowie słownika, w przeciwnym razie kontynuuj podobnie w prawej połowie słownika. Algorytm ten jest podobny do metody często stosowanej do wyszukiwania hasła w słowniku papierowym.

Czas polilogarytmiczny

Mówi się, że algorytm działa w czasie polilogarytmicznym, jeśli jego czas T ( n ) wynosi O ((log n ) k ) dla pewnej stałej k . Innym sposobem zapisania tego jest O (log k n ) .

Na przykład, uporządkowanie łańcucha macierzy można rozwiązać w czasie polilogarytmicznym na równoległej maszynie o swobodnym dostępie , a wykres można określić jako planarny w sposób w pełni dynamiczny w czasie O (log 3 n ) na operację wstawiania/usuwania.

Czas podliniowy

Mówi się, że algorytm działa w czasie podliniowym (często pisanym w czasie podliniowym ), jeśli T ( n ) = o ( n ) . W szczególności dotyczy to algorytmów o złożoności czasowej określonej powyżej.

Typowe algorytmy, które są dokładne, a jednak działają w czasie podliniowym, wykorzystują przetwarzanie równoległe (jak ma to miejsce w przypadku obliczania wyznacznika macierzy NC 1 ) lub alternatywnie mają gwarantowane założenia dotyczące struktury wejściowej (jak robi to logarytmiczne przeszukiwanie binarne w czasie i wiele algorytmów utrzymania drzewa) . Jednak języki formalne, takie jak zbiór wszystkich łańcuchów, które mają 1-bit w pozycji wskazanej przez pierwsze bity log( n ) łańcucha mogą zależeć od każdego bitu danych wejściowych, a mimo to być obliczalne w czasie podliniowym.

Specyficzny termin „ algorytm czasu podliniowego” jest zwykle zarezerwowany dla algorytmów, które różnią się od powyższego, ponieważ są uruchamiane na klasycznych modelach maszyn szeregowych i nie są dozwolone wcześniejsze założenia na wejściu. Mogą być jednak losowane i rzeczywiście muszą być losowane dla wszystkich zadań poza najbardziej trywialnymi.

Ponieważ taki algorytm musi dostarczyć odpowiedź bez czytania całego wejścia, jego szczegóły w dużym stopniu zależą od dostępu do danych wejściowych. Zwykle dla wejścia reprezentowanego jako ciąg binarny b 1 ,…, b k zakłada się, że algorytm może w czasie O (1) zażądać i otrzymać wartość b i dla dowolnego i .

Algorytmy czasu podliniowego są zazwyczaj losowe i zapewniają tylko przybliżone rozwiązania. W rzeczywistości można łatwo udowodnić, że właściwość ciągu binarnego zawierającego tylko zera (i żadnych jedynek) nie jest rozstrzygalna za pomocą (nieprzybliżonego) algorytmu czasu podliniowego. Algorytmy czasu podliniowego pojawiają się naturalnie w badaniu właściwości .

Czas liniowy

Mówi się, że algorytm przyjmuje czas liniowy lub czas O ( n ) , jeśli jego złożoność czasowa wynosi O ( n ) . Nieformalnie oznacza to, że czas działania rośnie co najwyżej liniowo wraz z rozmiarem danych wejściowych. Dokładniej, oznacza to, że istnieje stała c taka, że ​​czas działania wynosi co najwyżej cn dla każdego wejścia o rozmiarze n . Na przykład procedura dodawania wszystkich elementów listy wymaga czasu proporcjonalnego do długości listy, jeśli czas dodawania jest stały lub przynajmniej ograniczony przez stałą.

Czas liniowy jest najlepszą możliwą złożonością czasową w sytuacjach, gdy algorytm musi sekwencyjnie odczytywać całe dane wejściowe. Dlatego zainwestowano wiele badań w odkrycie algorytmów wykazujących czas liniowy lub przynajmniej prawie liniowy. Badania te obejmują zarówno metody programowe, jak i sprzętowe. Istnieje kilka technologii sprzętowych, które wykorzystują do tego równoległość . Przykładem jest pamięć adresowalna treści . Ta koncepcja czasu liniowego jest używana w algorytmach dopasowywania ciągów, takich jak algorytm Boyera-Moore'a i algorytm Ukkonena .

Czas quasilinearny

Mówi się, że algorytm działa w czasie quasilinearnym (określanym również jako log-linear time ), jeśli T ( n ) = O ( n log k n ) dla pewnej dodatniej stałej k ; czas liniowy to przypadek k = 1 . Używając miękkiej notacji O te algorytmy to Õ( n ). Algorytmy czasu quasilinearnego są również O ( n 1 + ε ) dla każdej stałej ε > 0, a zatem działają szybciej niż jakikolwiek algorytm czasu wielomianowego, którego ograniczenie czasowe zawiera wyraz n c dla dowolnego c > 1 .

Algorytmy działające w czasie quasilinearnym obejmują:

W wielu przypadkach czas działania n log n jest po prostu wynikiem wykonania operacji Θ(log n ) n razy (o notacji patrz notacja Big O § Family of Bachmann-Landau ). Na przykład sortowanie drzewa binarnego tworzy drzewo binarne , wstawiając każdy element tablicy o rozmiarze n jeden po drugim. Ponieważ operacja wstawiania na samobalansującym drzewie wyszukiwania binarnego zajmuje czas O (log n ), cały algorytm zajmuje czas O ( n log n ) .

Sortowanie porównawcze wymaga co najmniej Ω( n log n ) porównań w najgorszym przypadku, ponieważ log( n !) = Θ( n log n ) , według aproksymacji Stirlinga . Często wynikają one również z relacji rekurencyjności T ( n ) = 2 T ( n /2) + O ( n ) .

Czas podkwadratowy

Algorytm nazywa się subquadratic razem , gdy T ( n ) = O ( N 2 ) .

Na przykład proste, oparte na porównaniach algorytmy sortowania są kwadratowe (np. sortowanie przez wstawianie ), ale można znaleźć bardziej zaawansowane algorytmy, które są podkwadratowe (np. sortowanie przez powłokę ). Żadne sortowania ogólnego przeznaczenia nie przebiegają w czasie liniowym, ale zmiana z kwadratowej na podkwadratową ma ogromne znaczenie praktyczne.

Czas wielomianowy

Algorytm nazywa się z wielomianu czasie , gdy jego czas działania jest górną ograniczoną przez wielomian ekspresji w wielkości wejściowych dla algorytmu, który jest, T ( n ) = O ( n k ) dla pewnej dodatnią stałą k . Problemy , dla których istnieje deterministyczny algorytm wielomianu czasu , należą do klasy złożoności P , która jest centralna w dziedzinie teorii złożoności obliczeniowej . Teza Cobhama stwierdza, że ​​czas wielomianowy jest synonimem „wykonalnego”, „wykonalnego”, „efektywnego” lub „szybkiego”.

Kilka przykładów algorytmów czasu wielomianowego:

  • Wybór porządek sortowania algorytm na n liczb całkowitych wykonuje operacje dla pewnej stałej A . Zatem działa w czasie i jest wielomianowym algorytmem czasu.
  • Wszystkie podstawowe operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie i porównywanie) można wykonywać w czasie wielomianowym.
  • Maksymalne dopasowania na wykresach można znaleźć w czasie wielomianowym.

Silnie i słabo wielomianowy czas

W niektórych kontekstach, zwłaszcza w optymalizacji , rozróżnia się algorytmy z czasem silnie wielomianowym i słabo wielomianowym . Te dwie koncepcje mają znaczenie tylko wtedy, gdy dane wejściowe algorytmów składają się z liczb całkowitych.

W arytmetycznym modelu obliczeń zdefiniowany jest czas silnie wielomianowy. W tym modelu obliczeń podstawowe operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie i porównywanie) wykonują krok jednostkowy w czasie, niezależnie od wielkości argumentów. Algorytm działa w czasie silnie wielomianowym, jeśli:

  1. liczba operacji w arytmetycznym modelu obliczeń jest ograniczona wielomianem liczby liczb całkowitych w instancji wejściowej; oraz
  2. przestrzeń wykorzystywana przez algorytm jest ograniczona wielomianem wielkości danych wejściowych.

Dowolny algorytm z tymi dwiema właściwościami może być przekształcony w algorytm wielomianowy przez zastąpienie operacji arytmetycznych odpowiednimi algorytmami do wykonywania operacji arytmetycznych na maszynie Turinga . Jeśli drugi z powyższych warunków nie jest spełniony, to nie jest to już prawdą. Biorąc pod uwagę liczbę całkowitą (która zajmuje przestrzeń proporcjonalną do n w modelu maszyny Turinga), możliwe jest obliczenie z n mnożeniami przy użyciu powtarzanego podniesienia do kwadratu . Jednak przestrzeń używana do reprezentowania jest proporcjonalna do , a zatem wykładnicza, a nie wielomianowa w przestrzeni używanej do reprezentowania danych wejściowych. Stąd nie jest możliwe przeprowadzenie tego obliczenia w czasie wielomianowym na maszynie Turinga, ale możliwe jest obliczenie tego wielomianu za pomocą wielu operacji arytmetycznych.

I odwrotnie, istnieją algorytmy, które działają w wielu krokach maszyny Turinga ograniczonych wielomianem o długości danych wejściowych zakodowanych binarnie, ale nie wykonują wielu operacji arytmetycznych ograniczonych wielomianem o liczbie liczb wejściowych. Euklidesowa algorytm do obliczania największego wspólnego dzielnika dwóch liczb całkowitych jest jednym z przykładów. Mając dwie liczby całkowite i , algorytm wykonuje operacje arytmetyczne na liczbach zawierających co najwyżej bity. Jednocześnie liczba operacji arytmetycznych nie może być ograniczona liczbą liczb całkowitych na wejściu (która jest w tym przypadku stała, na wejściu są zawsze tylko dwie liczby całkowite). Ze względu na tę ostatnią obserwację algorytm nie działa w czasie silnie wielomianowym. Jego prawdziwy czas pracy zależy od wielkościami i nie tylko na liczby całkowite w wejściu.

Mówi się, że algorytm, który działa w czasie wielomianowym, ale nie jest silnie wielomianowy, działa w czasie słabo wielomianowym . Dobrze znanym przykładem problemu, dla którego znany jest algorytm słabo wielomianowy, ale nie wiadomo, czy dopuszcza się algorytm silnie wielomianowy, jest programowanie liniowe . Czasu słabego wielomianu nie należy mylić z czasem pseudowielomianowym .

Klasy złożoności

Pojęcie czasu wielomianowego prowadzi do kilku klas złożoności w teorii złożoności obliczeniowej. Oto kilka ważnych klas zdefiniowanych za pomocą czasu wielomianowego.

P Klasa złożoności od problemów decyzyjnych , które mogą być rozwiązane na deterministycznej maszyny Turinga w czasie wielomianowym
NP Klasa złożoności problemów decyzyjnych, które można rozwiązać na niedeterministycznej maszynie Turinga w czasie wielomianowym
ZPP Klasa złożoności problemów decyzyjnych, które można rozwiązać z zerowym błędem na probabilistycznej maszynie Turinga w czasie wielomianowym
RP Klasa złożoności problemów decyzyjnych, które można rozwiązać z błędem jednostronnym na probabilistycznej maszynie Turinga w czasie wielomianowym.
BPP Klasa złożoności problemów decyzyjnych, które można rozwiązać z błędem dwustronnym na probabilistycznej maszynie Turinga w czasie wielomianowym
BQP Klasa złożoności problemów decyzyjnych, które można rozwiązać z błędem dwustronnym na kwantowej maszynie Turinga w czasie wielomianowym

P jest najmniejszą klasą złożoności czasowej na maszynie deterministycznej, która jest odporna na zmiany modelu maszyny. (Na przykład, zmiana z pojedynczej taśmy maszyny Turinga na maszynę multi-taśmy może prowadzić do kwadratowej SpeedUp, ale każdy algorytm, który działa w czasie wielomianowym pod jednym modelu robi też tak z drugiej strony.) Danej abstrakcyjnej maszyny woli mają klasę złożoności odpowiadającą problemom, które można rozwiązać w czasie wielomianowym na tej maszynie.

Czas superwielomianowy

Mówi się, że algorytm zajmuje czas superwielomianu, jeśli T ( n ) nie jest ograniczony powyżej żadnym wielomianem. Używając małej notacji omega , jest to ω ( n c ) czas dla wszystkich stałych c , gdzie n jest parametrem wejściowym, zazwyczaj liczbą bitów na wejściu.

Na przykład algorytm, który działa dla 2 n kroków na wejściu o rozmiarze n, wymaga czasu superwielomianowego (a dokładniej czasu wykładniczego).

Algorytm wykorzystujący zasoby wykładnicze jest wyraźnie superwielomianowy, ale niektóre algorytmy są bardzo słabo superwielomianowe. Na przykład test pierwszości Adleman-Pomerance-Rumely działa dla czasu n O (log log n ) na n- bitowych wejściach; rośnie szybciej niż jakikolwiek wielomian dla wystarczająco dużego n , ale rozmiar wejściowy musi stać się niepraktycznie duży, zanim nie będzie mógł zostać zdominowany przez wielomian o małym stopniu.

Algorytm wymagający czasu superwielomianowego leży poza klasą złożoności P . Teza Cobhama zakłada, że ​​algorytmy te są niepraktyczne, aw wielu przypadkach są. Ponieważ problem P kontra NP jest nierozwiązany, nie wiadomo, czy problemy NP-zupełne wymagają czasu superwielomianowego.

Czas quasi-wielomianowy

Algorytmy czasu quasi-wielomianowego to algorytmy, które działają dłużej niż czas wielomianowy, ale nie tak długo, jak czas wykładniczy. W najgorszym przypadku czas działania algorytmu czasu quasi-wielomianowego jest dla niektórych ustalony . Bo otrzymujemy wielomianowy algorytm czasu, ponieważ otrzymujemy podliniowy algorytm czasu.

Algorytmy czasu quasi-wielomianowego zwykle powstają w redukcji z problemu NP-trudnego do innego problemu. Na przykład, można wziąć instancję NP trudnego problemu, powiedzmy 3SAT , i przekonwertować ją na instancję innego problemu B, ale rozmiar instancji staje się . W takim przypadku ta redukcja nie dowodzi, że problem B jest NP-trudny; ta redukcja pokazuje tylko, że nie ma algorytmu czasu wielomianowego dla B, chyba że istnieje algorytm czasu quasi-wielomianowego dla 3SAT (a zatem wszystkich NP ). Podobnie, istnieją pewne problemy, dla których znamy algorytmy czasu quasi-wielomianowego, ale nie jest znany algorytm czasu wielomianowego. Takie problemy pojawiają się w algorytmach aproksymacyjnych; słynnym przykładem jest ukierunkowany problem drzewa Steinera , dla którego istnieje quasi-wielomianowy algorytm aproksymacji czasu osiągający współczynnik aproksymacji ( n jest liczbą wierzchołków), ale wykazanie istnienia takiego wielomianowego algorytmu czasu jest problemem otwartym.

Inne problemy obliczeniowe z rozwiązaniami opartymi na czasie quasi-wielomianowym, ale nie są znane rozwiązania oparte na czasie wielomianowym, obejmują problem zasadzonej kliki, w którym celem jest znalezienie dużej kliki w połączeniu kliki i grafu losowego . Chociaż quasi-wielomianowo rozwiązywalny, przypuszcza się, że problem zasadzonych kliki nie ma rozwiązania wielomianowego w czasie; Ta hipoteza osadzonej kliki została wykorzystana jako założenie o twardości obliczeniowej, aby udowodnić trudność kilku innych problemów w teorii gier obliczeniowych , testowaniu właściwości i uczeniu maszynowym .

Klasa złożoności QP obejmuje wszystkie problemy, które mają algorytmy czasu quasi-wielomianowego. Można go zdefiniować w kategoriach DTIME w następujący sposób.

Związek z problemami NP-zupełnymi

W teorii złożoności nierozwiązany problem P versus NP pyta, czy wszystkie problemy w NP mają algorytmy wielomianowe. Wszystkie najbardziej znane algorytmy rozwiązywania problemów NP-zupełnych , takie jak 3SAT itp., wymagają czasu wykładniczego. Rzeczywiście, przypuszcza się, że w przypadku wielu naturalnych problemów NP-zupełnych nie mają one algorytmów czasu podwykładniczego. Tutaj „czas podwykładniczy” oznacza drugą definicję przedstawioną poniżej. (Z drugiej strony, wiele problemów grafowych reprezentowanych w naturalny sposób przez macierze sąsiedztwa można rozwiązać w czasie podwykładniczym, ponieważ wielkość danych wejściowych jest kwadratem liczby wierzchołków.) Ta hipoteza (dla problemu k-SAT) jest znana jako hipoteza czasu wykładniczego . Ponieważ przypuszcza się, że problemy NP-zupełne nie mają algorytmów czasu quasi-wielomianowego, niektóre wyniki nieprzybliżeniowości w dziedzinie algorytmów aproksymacji zakładają, że problemy NP-zupełne nie mają algorytmów czasu quasi-wielomianowego. Na przykład zobacz znane wyniki nieprzybliżeniowości dla problemu z okładką zestawu .

Czas sub-wykładniczy

Termin czas podwykładniczy jest używany do wyrażenia, że ​​czas działania jakiegoś algorytmu może rosnąć szybciej niż jakikolwiek wielomian, ale nadal jest znacznie mniejszy niż wykładniczy. W tym sensie problemy, które mają algorytmy czasu podwykładniczego, są nieco bardziej wykonalne niż te, które mają tylko algorytmy wykładnicze. Dokładna definicja „podwykładniczego” nie jest ogólnie uzgodniona, a poniżej wymieniamy dwie najczęściej używane.

Pierwsza definicja

Mówi się, że problem można rozwiązać w czasie podwykładniczym, jeśli można go rozwiązać w czasie, którego logarytmy stają się mniejsze niż dowolny wielomian. Dokładniej, problem występuje w czasie podwykładniczym, jeśli dla każdego ε > 0 istnieje algorytm, który rozwiązuje problem w czasie O (2 n ε ). Zestawem wszystkich takich problemów jest klasa złożoności SUBEXP, którą można zdefiniować w kategoriach DTIME w następujący sposób.

To pojęcie sub-wykładnicze jest niejednorodne pod względem ε w tym sensie, że ε nie jest częścią danych wejściowych i każde ε może mieć własny algorytm rozwiązania problemu.

Druga definicja

Niektórzy autorzy definiują czas podwykładniczy jako czas działania w 2o ( n ) . Ta definicja pozwala na dłuższe czasy działania niż pierwsza definicja czasu podwykładniczego. Przykładem takiego algorytmu czasu podwykładniczego jest najbardziej znany klasyczny algorytm faktoryzacji liczb całkowitych, ogólne sito pola liczbowego , które działa w czasie około , gdzie długość wejścia wynosi n . Innym przykładem był problem izomorfizmu grafów , który rozwiązał najbardziej znany algorytm z lat 1982-2016 . Jednak na STOC 2016 zaprezentowano algorytm quasi-wielomianowy.

To ma znaczenie, czy algorytm może być podwykładniczy w rozmiarze instancji, liczbie wierzchołków lub liczbie krawędzi. W parametryzowanego złożoności , ta różnica jest wyraźnie rozważając par z problemów decyzyjnych i parametrów k . SUBEPT jest klasą wszystkich sparametryzowanych problemów, które działają w czasie w sposób podwykładniczy w k i wielomianowy w rozmiarze wejściowym n :

Dokładniej, SUBEPT jest klasą wszystkich sparametryzowanych problemów, dla których istnieje funkcja obliczeniowa z algorytmem, który decyduje o L w czasie .

Hipoteza czasu wykładniczego

Wykładniczy hipoteza czas ( ETH ) jest 3SAT problem spełnialności Boole'a formułach spojówek postaci normalnej, z co najwyżej, trzech literałami według klauzuli i n zmiennych, nie może być rozwiązany w czasie 2 O ( n ) . Dokładniej, hipoteza jest taka, że ​​istnieje pewna bezwzględna stała c > 0 taka, że ​​3SAT nie może być rozstrzygnięty w czasie 2 cn przez żadną deterministyczną maszynę Turinga. Z m oznaczającym liczbę klauzul, ETH jest równoważne hipotezie, że k SAT nie może być rozwiązane w czasie 2 o ( m ) dla dowolnej liczby całkowitej k ≥ 3 . Hipoteza czasu wykładniczego implikuje P ≠ NP .

Czas wykładniczy

Mówi się, że algorytm jest czasem wykładniczym , jeśli T ( n ) jest górnie ograniczone przez 2 poly( n ) , gdzie poly( n ) jest jakimś wielomianem w n . Bardziej formalnie, algorytm jest wykładniczym czasem, jeśli T ( n ) jest ograniczone przez O (2 n k ) dla pewnej stałej k . Problemy, które dopuszczają algorytmy czasu wykładniczego na deterministycznej maszynie Turinga, tworzą klasę złożoności znaną jako EXP .

Czasami czas wykładniczy jest używany w odniesieniu do algorytmów, które mają T ( n ) = 2 O ( n ) , gdzie wykładnik jest co najwyżej funkcją liniową n . Daje to początek klasie złożoności E .

Czas czynnikowy

Przykładem algorytmu działającego w czasie czynnikowym jest bogosort , notorycznie nieefektywny algorytm sortowania oparty na próbach i błędach . Bogosort sortuje listę n elementów przez wielokrotne tasowanie listy, aż zostanie odnaleziona do posortowania. W przeciętnym przypadku każde przejście przez algorytm bogosort sprawdza jeden z n ! zamówienia n pozycji. Jeśli pozycje są różne, sortowana jest tylko jedna taka kolejność. Bogosort dzieli dziedzictwo z twierdzeniem o nieskończonej małpie .

Podwójny czas wykładniczy

Mówi się, że algorytm jest podwójnie wykładniczy, jeśli T ( n ) jest górnie ograniczone przez 2 2 poly( n ) , gdzie poly( n ) jest jakimś wielomianem w n . Takie algorytmy należą do klasy złożoności 2-EXPTIME .

Dobrze znane algorytmy podwójnego czasu wykładniczego obejmują:

Zobacz też

Bibliografia