Teoria złożoności obliczeniowej - Computational complexity theory

Teoria złożoności obliczeniowej koncentruje się na klasyfikowaniu problemów obliczeniowych zgodnie z ich wykorzystaniem zasobów i powiązaniu tych klas ze sobą. Problem obliczeniowy to zadanie rozwiązywane przez komputer. Problem obliczeniowy można rozwiązać przez mechaniczne zastosowanie kroków matematycznych, takich jak algorytm .

Problem jest uważany za z natury trudny, jeśli jego rozwiązanie wymaga znacznych zasobów, niezależnie od zastosowanego algorytmu. Teoria formalizuje tę intuicję, wprowadzając matematyczne modele obliczeniowe do badania tych problemów i kwantyfikowania ich złożoności obliczeniowej , tj. ilości zasobów potrzebnych do ich rozwiązania, takich jak czas i pamięć. Stosowane są również inne miary złożoności, takie jak ilość komunikacji (używana w złożoności komunikacji ), liczba bramek w obwodzie (używana w złożoności obwodu ) i liczba procesorów (używana w obliczeniach równoległych ). Jedną z ról teorii złożoności obliczeniowej jest określenie praktycznych ograniczeń tego, co komputery mogą, a czego nie mogą zrobić. Problem P versus NP , jeden z siedmiu problemów Nagród Milenijnych , poświęcony jest dziedzinie złożoności obliczeniowej.

Ściśle pokrewnymi dziedzinami informatyki teoretycznej są analiza algorytmów i teoria obliczalności . Kluczowym rozróżnieniem między analizą algorytmów a teorią złożoności obliczeniowej jest to, że ta pierwsza poświęcona jest analizie ilości zasobów potrzebnych danemu algorytmowi do rozwiązania problemu, podczas gdy ta druga zadaje bardziej ogólne pytanie o wszystkie możliwe algorytmy, które można wykorzystać do rozwiązać ten sam problem. Dokładniej, teoria złożoności obliczeniowej stara się klasyfikować problemy, które mogą lub nie mogą być rozwiązane przy odpowiednio ograniczonych zasobach. Z kolei nakładanie ograniczeń na dostępne zasoby jest tym, co odróżnia złożoność obliczeniową od teorii obliczalności: ta ostatnia stawia pytanie, jakie problemy można w zasadzie rozwiązać algorytmicznie.

Problemy obliczeniowe

Objazdowa wycieczka komiwojażera po 14 niemieckich miastach.

Instancje problemowe

Obliczeniowa problemu może być traktowana jako zbiór nieskończonej przypadkach wraz z zestawem (ewentualnie) z pustym rozwiązania dla każdego przypadku. Ciąg wejściowy dla problemu obliczeniowego jest określany jako instancja problemu i nie należy go mylić z samym problemem. W teorii złożoności obliczeniowej problem odnosi się do abstrakcyjnego pytania do rozwiązania. Natomiast przykładem tego problemu jest raczej konkretna wypowiedź, która może służyć jako wkład do problemu decyzyjnego. Rozważmy na przykład problem testowania pierwszości . Instancją jest liczba (np. 15), a rozwiązaniem jest „tak”, jeśli liczba jest liczbą pierwszą, a „nie” w przeciwnym razie (w tym przypadku 15 nie jest liczbą pierwszą, a odpowiedź brzmi „nie”). Innymi słowy, instancja jest konkretnym wejściem problemu, a rozwiązaniem jest wyjście odpowiadające danemu wejściu.

Aby jeszcze bardziej podkreślić różnicę między problemem a instancją, rozważmy następujący przykład wersji decyzyjnej problemu komiwojażera : Czy istnieje trasa o długości co najwyżej 2000 kilometrów przebiegająca przez wszystkie 15 największych miast Niemiec? Ilościowa odpowiedź na ten konkretny problem jest mało przydatna do rozwiązywania innych przypadków problemu, takich jak prośba o podróż w obie strony przez wszystkie miejsca w Mediolanie, których łączna długość wynosi co najwyżej 10 km. Z tego powodu teoria złożoności zajmuje się problemami obliczeniowymi, a nie konkretnymi przypadkami problemów.

Reprezentowanie instancji problemowych

Rozważając problemy obliczeniowe, instancją problemu jest ciąg znaków nad alfabetem . Zwykle przyjmuje się, że alfabet jest alfabetem binarnym (tj. zbiorem {0,1}), a zatem łańcuchy są bitstrings . Podobnie jak w prawdziwym komputerze , obiekty matematyczne inne niż ciągi bitów muszą być odpowiednio zakodowane. Na przykład liczby całkowite mogą być reprezentowane w notacji binarnej , a wykresy mogą być kodowane bezpośrednio przez ich macierze sąsiedztwa lub przez kodowanie ich list sąsiedztwa w formacie binarnym.

Mimo że niektóre dowody twierdzeń opartych na teorii złożoności regularnie zakładają konkretny wybór kodowania danych wejściowych, staramy się utrzymać dyskusję na tyle abstrakcyjną, aby była niezależna od wyboru kodowania. Można to osiągnąć poprzez zapewnienie, że różne reprezentacje mogą być skutecznie przekształcane w siebie.

Problemy decyzyjne jako języki formalne

Problem decyzyjny ma tylko dwa możliwe wyjścia, tak lub nie (lub na przemian 1 lub 0), na każdym wejściu.

Problemy decyzyjne są jednym z centralnych przedmiotów badań w teorii złożoności obliczeniowej. Problem decyzyjny jest specjalnym rodzajem problemu obliczeniowego, na który odpowiedzią jest tak lub nie , albo alternatywnie 1 lub 0. Problem decyzyjny może być postrzegany jako język formalny , w którym elementy języka są instancjami, których wyjściem jest tak, oraz nieczłonkowskimi są te instancje, których wyjście to nie. Celem jest ustalenie za pomocą algorytmu , czy dany ciąg wejściowy należy do rozważanego języka formalnego. Jeśli algorytm decydujący o tym problemie zwróci odpowiedź tak , mówi się, że algorytm akceptuje ciąg wejściowy, w przeciwnym razie mówi się, że odrzuca dane wejściowe.

Przykład problemu decyzyjnego jest następujący. Dane wejściowe to dowolny wykres . Problem polega na rozstrzygnięciu, czy dany graf jest połączony, czy nie. Językiem formalnym związanym z tym problemem decyzyjnym jest więc zbiór wszystkich połączonych grafów — aby uzyskać dokładną definicję tego języka, trzeba zdecydować, w jaki sposób grafy są kodowane jako łańcuchy binarne.

Problemy funkcjonalne

Problemem funkcja jest obliczeniowa problemu gdzie jedno wyjście (z ogólnej funkcji oczekuje się) dla każdego wejścia, ale wyjście jest bardziej złożona niż w przypadku problemu decyzyjnego -to jest wyjście nie jest tylko tak lub nie. Godne uwagi przykłady obejmują problem komiwojażera i problem faktoryzacji liczb całkowitych .

Kusząca jest myśl, że pojęcie problemów funkcjonalnych jest znacznie bogatsze niż pojęcie problemów decyzyjnych. Jednak tak nie jest, ponieważ problemy funkcjonalne mogą zostać przekształcone w problemy decyzyjne. Na przykład mnożenie dwóch liczb całkowitych może być wyrażone jako zbiór trójek ( a ,  b ,  c ) tak, że zachodzi relacja a  ×  b  =  c . Ustalenie, czy dana trójka należy do tego zbioru, odpowiada rozwiązaniu problemu mnożenia dwóch liczb.

Mierzenie rozmiaru instancji

Aby zmierzyć trudność rozwiązania problemu obliczeniowego, można chcieć zobaczyć, ile czasu potrzebuje najlepszy algorytm na rozwiązanie problemu. Jednak czas działania może generalnie zależeć od instancji. W szczególności rozwiązanie większych instancji będzie wymagało więcej czasu. W ten sposób czas potrzebny do rozwiązania problemu (lub wymagana przestrzeń lub dowolny środek złożoności) jest obliczany jako funkcja rozmiaru instancji. Zwykle przyjmuje się, że jest to rozmiar danych wejściowych w bitach. Teoria złożoności interesuje się skalowaniem algorytmów wraz ze wzrostem wielkości danych wejściowych. Na przykład w przypadku problemu z ustaleniem, czy graf jest połączony, o ile więcej czasu zajmuje rozwiązanie problemu dla grafu o 2 n wierzchołkach w porównaniu z czasem potrzebnym na graf o n wierzchołkach?

Jeśli wielkość wejściowa wynosi n , potrzebny czas można wyrazić jako funkcję n . Ponieważ czas pobierany na różnych wejściach o tym samym rozmiarze może być różny, złożoność czasowa najgorszego przypadku T( n ) jest definiowana jako maksymalny czas pobierany na wszystkich wejściach o rozmiarze n . Jeśli T( n ) jest wielomianem w n , to algorytm nazywamy wielomianowym algorytmem czasu . Teza Cobhama twierdzi, że problem można rozwiązać za pomocą wykonalnej ilości zasobów, jeśli dopuszcza algorytm wielomianowy.

Modele maszyn i miary złożoności

Maszyna Turinga

Ilustracja maszyny Turinga

Maszyna Turinga to model matematyczny ogólnej maszyny obliczeniowej. Jest to urządzenie teoretyczne, które manipuluje symbolami zawartymi na pasku taśmy. Maszyny Turinga nie są pomyślane jako praktyczna technologia obliczeniowa, ale raczej jako ogólny model maszyny liczącej – od zaawansowanego superkomputera po matematyka z ołówkiem i papierem. Uważa się, że jeśli problem można rozwiązać za pomocą algorytmu, istnieje maszyna Turinga, która go rozwiązuje. W istocie jest to stwierdzenie tezy Kościoła-Turinga . Co więcej, wiadomo, że wszystko, co można obliczyć na innych znanych nam dzisiaj modelach obliczeniowych, takich jak maszyna RAM , Gra w życie Conwaya , automaty komórkowe czy dowolny język programowania, można obliczyć na maszynie Turinga. Ponieważ maszyny Turinga są łatwe do analizy matematycznej i uważa się, że są tak potężne, jak każdy inny model obliczeń, maszyna Turinga jest najczęściej używanym modelem w teorii złożoności.

Wiele typów maszyn Turinga jest używanych do definiowania klas złożoności, takich jak deterministyczne maszyny Turinga , probabilistyczne maszyny Turinga , niedeterministyczne maszyny Turinga , kwantowe maszyny Turinga , symetryczne maszyny Turinga i przemienne maszyny Turinga . W zasadzie wszystkie są równie potężne, ale gdy zasoby (takie jak czas lub przestrzeń) są ograniczone, niektóre z nich mogą być potężniejsze niż inne.

Deterministyczna maszyna Turinga jest najbardziej podstawową maszyną Turinga, która używa ustalonego zestawu reguł do określania swoich przyszłych działań. Probabilistyczna maszyna Turinga to deterministyczna maszyna Turinga z dodatkowym zapasem losowych bitów. Umiejętność podejmowania probabilistycznych decyzji często pomaga algorytmom skuteczniej rozwiązywać problemy. Algorytmy używające losowych bitów nazywane są algorytmami randomizowanymi . Niedeterministyczna maszyna Turinga to deterministyczna maszyna Turinga z dodatkową cechą niedeterminizmu, która pozwala maszynie Turinga na wiele możliwych przyszłych działań z danego stanu. Jednym ze sposobów postrzegania niedeterminizmu jest to, że maszyna Turinga rozgałęzia się na wiele możliwych ścieżek obliczeniowych na każdym kroku, a jeśli rozwiąże problem w którejkolwiek z tych gałęzi, mówi się, że rozwiązała problem. Oczywiście ten model nie ma być fizycznie realizowalnym modelem, jest tylko teoretycznie interesującą maszyną abstrakcyjną, która daje początek szczególnie interesującym klasom złożoności. Aby zapoznać się z przykładami, zobacz algorytm niedeterministyczny .

Inne modele maszyn

W literaturze zaproponowano wiele modeli maszyn różniących się od standardowych wielotaśmowych maszyn Turinga , np . maszyny o swobodnym dostępie . Być może zaskakujące jest to, że każdy z tych modeli można przekonwertować na inny bez zapewniania dodatkowej mocy obliczeniowej. Czas i zużycie pamięci tych alternatywnych modeli może się różnić. Wspólną cechą wszystkich tych modeli jest to, że maszyny działają deterministycznie .

Jednak niektóre problemy obliczeniowe są łatwiejsze do przeanalizowania pod kątem bardziej nietypowych zasobów. Na przykład niedeterministyczna maszyna Turinga jest modelem obliczeniowym, który może rozgałęziać się, aby jednocześnie sprawdzić wiele różnych możliwości. Niedeterministyczna maszyna Turinga ma bardzo mało wspólnego z tym, jak fizycznie chcemy obliczać algorytmy, ale jej rozgałęzienie dokładnie wychwytuje wiele modeli matematycznych, które chcemy analizować, więc niedeterministyczny czas jest bardzo ważnym zasobem w analizie problemów obliczeniowych .

Miary złożoności

Aby dokładnie zdefiniować, co to znaczy rozwiązać problem przy użyciu określonej ilości czasu i przestrzeni, stosuje się model obliczeniowy, taki jak deterministyczna maszyna Turinga . Czas wymagany przez deterministycznej maszyny Turinga M na wejściu x oznacza całkowitą liczbę przejść państwowych, lub etapów, maszyna sprawia, zanim on hamująco i wysyła odpowiedź ( „tak” lub „nie”). Mówi się, że maszyna Turinga M działa w czasie f ( n ), jeśli czas wymagany przez M na każdym wejściu o długości n wynosi co najwyżej f ( n ). Problem decyzyjny A można rozwiązać w czasie f ( n ), jeśli istnieje maszyna Turinga działająca w czasie f ( n ), która rozwiązuje problem. Ponieważ teoria złożoności jest zainteresowana klasyfikacją problemów na podstawie ich trudności, definiuje się zestawy problemów w oparciu o pewne kryteria. Na przykład zbiór problemów możliwych do rozwiązania w czasie f ( n ) na deterministycznej maszynie Turinga jest następnie oznaczany przez DTIME ( f ( n )).

Analogiczne definicje można utworzyć dla wymagań przestrzennych. Chociaż czas i przestrzeń są najbardziej znanymi zasobami złożoności, każda miara złożoności może być postrzegana jako zasób obliczeniowy. Miary złożoności są bardzo ogólnie zdefiniowane przez aksjomaty złożoności Bluma . Inne środki stosowane w złożoność teorii złożoności to złożoność komunikacji , złożoność obwodu i drzewo decyzyjne złożoności .

Złożoność algorytmu jest często wyrażana za pomocą notacji big O .

Złożoność najlepszego, najgorszego i przeciętnego przypadku

Wizualizacja algorytmu szybkiego sortowania o średniej wydajności spraw . ${\ Displaystyle {\ mathcal {O}} (n \ log n)}$

Najlepszy, najgorszy przypadek i średnia złożoność odnoszą się do trzech różnych sposobów pomiaru złożoność czasową (lub jakiegokolwiek innego środka złożoność) z różnych źródeł w tym samym rozmiarze. Ponieważ niektóre dane wejściowe o rozmiarze n mogą być szybsze do rozwiązania niż inne, definiujemy następujące złożoności:

1. Złożoność najlepszego przypadku: jest to złożoność rozwiązania problemu dla najlepszego wejścia o rozmiarze n .
2. Złożoność średniej wielkości: Jest to złożoność rozwiązywania problemu średnio. Ta złożoność jest definiowana tylko w odniesieniu do rozkładu prawdopodobieństwa na danych wejściowych. Na przykład, jeśli zakłada się, że wszystkie dane wejściowe o tej samej wielkości są jednakowo prawdopodobne, że wystąpią, średnia złożoność przypadku może być zdefiniowana w odniesieniu do równomiernego rozkładu wszystkich danych wejściowych o rozmiarze n .
3. Analiza amortyzowana : Analiza amortyzowana uwzględnia zarówno kosztowne, jak i mniej kosztowne operacje razem w całej serii operacji algorytmu.
4. Złożoność najgorszego przypadku: jest to złożoność rozwiązania problemu dla najgorszego wejścia o rozmiarze n .

Porządek od taniego do drogiego jest: najlepszy, średni (o dyskretnej, równomiernej dystrybucji ), amortyzowany, najgorszy.

Rozważmy na przykład deterministyczny algorytm sortowania quicksort . Rozwiązuje to problem sortowania listy liczb całkowitych podawanych jako dane wejściowe. Najgorszy przypadek ma miejsce, gdy element przestawny jest zawsze największą lub najmniejszą wartością na liście (więc lista nigdy nie jest dzielona). W tym przypadku algorytm zajmuje czas O ( n ² ). Jeśli założymy, że wszystkie możliwe permutacje listy wejściowej są jednakowo prawdopodobne, średni czas potrzebny na sortowanie wynosi O( n log n ). Najlepszy przypadek ma miejsce, gdy każdy obrót dzieli listę na pół, co również wymaga czasu O( n log n ).

Górne i dolne granice złożoności problemów

Aby sklasyfikować czas obliczeń (lub podobne zasoby, takie jak zużycie przestrzeni), pomocne jest wykazanie górnych i dolnych granic maksymalnego czasu wymaganego przez najbardziej wydajny algorytm do rozwiązania danego problemu. Złożoność algorytmu jest zwykle uważana za złożoność najgorszego przypadku, chyba że określono inaczej. Analiza konkretnego algorytmu należy do dziedziny analizy algorytmów . Aby pokazać górną granicę T ( n ) złożoności czasowej problemu, wystarczy wykazać, że istnieje określony algorytm, którego czas wykonania wynosi najwyżej T ( n ). Jednak udowodnienie dolnych granic jest znacznie trudniejsze, ponieważ dolne granice określają wszystkie możliwe algorytmy, które rozwiązują dany problem. Wyrażenie „wszystkie możliwe algorytmy” obejmuje nie tylko algorytmy znane dzisiaj, ale każdy algorytm, który może zostać odkryty w przyszłości. Pokazanie dolnej granicy T ( n ) dla problemu wymaga wykazania, że ​​żaden algorytm nie może mieć złożoności czasowej mniejszej niż T ( n ).

Granice górne i dolne są zwykle określane przy użyciu notacji dużego O , która ukrywa czynniki stałe i wyrazy mniejsze. Uniezależnia to granice od konkretnych szczegółów zastosowanego modelu obliczeniowego. Na przykład, jeśli T ( n ) = 7 n ²  + 15 n  + 40 , w notacji z dużym O piszemy T ( n ) = O( n ² ).

Klasy złożoności

Definiowanie klas złożoności

Klasa złożoności to zbiór problemów związanych z nimi komplikacji. Prostsze klasy złożoności są definiowane przez następujące czynniki:

• Rodzaj problemu obliczeniowego: Najczęściej stosowanymi problemami są problemy decyzyjne. Jednak złożoność klasy mogą być definiowane na podstawie problemów funkcyjnych , licząc problemów , problemów optymalizacyjnych , problemy obietnica , etc.
• Model obliczeń: Najpopularniejszym modelem obliczeń jest deterministyczna maszyna Turinga, ale wiele klas złożoności opiera się na niedeterministycznych maszynach Turinga, obwodach boolowskich , kwantowych maszynach Turinga , obwodach monotonicznych itp.
• Zasób (lub zasoby), który jest ograniczony i granica: te dwie właściwości są zwykle określane razem, takie jak „czas wielomianu”, „przestrzeń logarytmiczna”, „stała głębokość” itp.

Niektóre klasy złożoności mają skomplikowane definicje, które nie pasują do tego frameworka. Tak więc typowa klasa złożoności ma definicję podobną do następującej:

Zbiór problemów decyzyjnych rozwiązywanych przez deterministyczną maszynę Turinga w czasie f ( n ). (Ta klasa złożoności jest znana jako DTIME( f ( n ))).

Ale ograniczenie powyższego czasu obliczeń przez pewną konkretną funkcję f ( n ) często daje klasy złożoności, które zależą od wybranego modelu maszyny. Na przykład język { xx | x jest dowolnym ciągiem binarnym} można rozwiązać w czasie liniowym na wielotaśmowej maszynie Turinga, ale koniecznie wymaga czasu kwadratowego w modelu jednotaśmowych maszyn Turinga. Jeśli dopuścimy wielomianowe zmiany w czasie wykonywania, teza Cobhama-Edmondsa stwierdza, że ​​„złożoności czasowe w dowolnych dwóch rozsądnych i ogólnych modelach obliczeń są wielomianowo powiązane” ( Goldreich 2008 , rozdział 1.2). Stanowi to podstawę dla klasy złożoności P , która jest zbiorem problemów decyzyjnych rozwiązywanych przez deterministyczną maszynę Turinga w czasie wielomianowym. Odpowiednim zestawem problemów funkcjonalnych jest FP .

Ważne klasy złożoności

Reprezentacja relacji między klasami złożoności

Wiele ważnych klas złożoności można zdefiniować, ograniczając czas lub przestrzeń używaną przez algorytm. Niektóre ważne klasy złożoności problemów decyzyjnych zdefiniowanych w ten sposób są następujące:

Klasy przestrzeni logarytmicznej (koniecznie) nie uwzględniają przestrzeni potrzebnej do przedstawienia problemu.

Okazuje się, że PSPACE = NPSPACE i EXPSPACE = NEXPSPACE według twierdzenia Savitcha .

Inne ważne klasy złożoności obejmują BPP , ZPP i RP , które są definiowane przy użyciu probabilistycznych maszyn Turinga ; AC i NC , które są definiowane za pomocą obwodów logicznych; oraz BQP i QMA , które są definiowane za pomocą kwantowych maszyn Turinga. #P to ważna klasa złożoności problemów liczenia (nie problemów decyzyjnych). Klasy takie jak IP i AM są definiowane przy użyciu interaktywnych systemów dowodowych . ALL jest klasą wszystkich problemów decyzyjnych.

Twierdzenia o hierarchii

Dla tak zdefiniowanych klas złożoności pożądane jest udowodnienie, że rozluźnienie wymagań dotyczących (powiedzmy) czasu obliczeń rzeczywiście definiuje większy zestaw problemów. W szczególności, chociaż DTIME( n ) jest zawarte w DTIME( n ² ), warto wiedzieć, czy włączenie jest ścisłe. W przypadku wymagań dotyczących czasu i przestrzeni, odpowiedzi na takie pytania dają odpowiednio twierdzenia o hierarchii czasu i przestrzeni. Nazywane są twierdzeniami o hierarchii, ponieważ indukują odpowiednią hierarchię na klasach zdefiniowanych przez ograniczanie odpowiednich zasobów. Tak więc istnieją pary klas złożoności, takie, że jedna jest prawidłowo zawarta w drugiej. Po wydedukowaniu tak odpowiednich wtrąceń zbioru możemy przystąpić do ilościowych stwierdzeń o ile więcej czasu lub przestrzeni potrzeba więcej, aby zwiększyć liczbę problemów, które można rozwiązać.

Dokładniej, twierdzenie o hierarchii czasu mówi, że:

${\ Displaystyle {\ mathsf {DTIME}}{\ duży (} f (n) {\ duży)} \ subsetneq {\ mathsf {DTIME}} {\ duży (} f (n) \ cdot \ log ^ {2} (f(n)){\duży )}}$.

Na przestrzeni hierarchia twierdzenie członkowskich, które

${\displaystyle {\mathsf {DSPACE}}{\duży (}f(n){\duży)}\subsetneq {\mathsf {DSPACE}}{\duży (}f(n)\cdot \log(f(n) )){\duża )}}$.

Twierdzenia o hierarchii czasu i przestrzeni stanowią podstawę większości wyników separacji klas złożoności. Na przykład twierdzenie o hierarchii czasu mówi nam, że P jest ściśle zawarte w EXPTIME, a twierdzenie o hierarchii przestrzeni mówi nam, że L jest ściśle zawarte w PSPACE.

Zmniejszenie

Wiele klas złożoności definiuje się za pomocą pojęcia redukcji. Redukcja to przekształcenie jednego problemu w inny. Ujmuje nieformalne pojęcie, że problem jest co najwyżej tak trudny, jak inny problem. Na przykład, jeśli problem X można rozwiązać za pomocą algorytmu dla Y , X nie jest trudniejsze niż Y i mówimy, że X redukuje się do Y . Istnieje wiele różnych typów redukcji, opartych na metodzie redukcji, takich jak redukcja Cooka, redukcja Karpa i redukcja Levina, oraz ograniczenia złożoności redukcji, takie jak redukcja wielomianowa lub redukcja przestrzeni logarytmicznej .

Najczęściej stosowaną redukcją jest redukcja wielomianowa. Oznacza to, że proces redukcji zajmuje czas wielomianowy. Na przykład problem kwadratury liczby całkowitej można sprowadzić do problemu mnożenia dwóch liczb całkowitych. Oznacza to, że algorytm mnożenia dwóch liczb całkowitych może być użyty do podniesienia liczby całkowitej do kwadratu. Rzeczywiście, można to zrobić, podając te same dane wejściowe do obu danych wejściowych algorytmu mnożenia. Widzimy więc, że kwadratura nie jest trudniejsza niż mnożenie, ponieważ kwadratura może być sprowadzona do mnożenia.

To motywuje koncepcję problemu, który jest trudny dla klasy złożoności. Problem X jest trudny dla klasy problemów C, jeśli każdy problem w C można zredukować do X . Zatem żaden problem w C nie jest trudniejszy niż X , ponieważ algorytm dla X pozwala nam rozwiązać dowolny problem w C . Pojęcie trudnych problemów zależy od rodzaju zastosowanej redukcji. W przypadku klas złożoności większych niż P, powszechnie stosuje się redukcje wielomianowe. W szczególności zbiór problemów trudnych dla NP jest zbiorem problemów NP-trudnych .

Jeśli problem X znajduje się w C i jest trudny dla C , wtedy mówi się, że X jest kompletny dla C . Oznacza to, że X jest najtrudniejszym problemem w C . (Ponieważ wiele problemów może być równie trudnych, można by powiedzieć, że X jest jednym z najtrudniejszych problemów w C .) Zatem klasa problemów NP-zupełnych zawiera najtrudniejsze problemy w NP, w tym sensie, że są to te, które są najbardziej prawdopodobne. nie być w P. Ponieważ problem P = NP nie jest rozwiązany, możliwość zredukowania znanego problemu NP-zupełnego, Π ₂ , do innego problemu, Π ₁ , wskazywałaby, że nie ma znanego rozwiązania wielomianowego dla Π ₁ . Dzieje się tak, ponieważ rozwiązanie wielomianowe dla Π ₁ dałoby rozwiązanie wielomianowe dla Π ₂ . Podobnie, ponieważ wszystkie problemy NP można zredukować do zbioru, znalezienie problemu NP-zupełnego, który można rozwiązać w czasie wielomianowym, oznaczałoby, że P = NP.

Ważne otwarte problemy

Schemat klas złożoności pod warunkiem, że P ≠ NP. Istnienie problemów w NP poza zarówno P, jak i NP-zupełnym w tym przypadku zostało stwierdzone przez Ladnera.

Problem P kontra NP

Klasa złożoności P jest często postrzegana jako matematyczna abstrakcja modelująca te zadania obliczeniowe, które dopuszczają wydajny algorytm. Ta hipoteza nazywa się tezą Cobhama-Edmondsa . Klasa złożoności NP , z drugiej strony, zawiera wiele problemów, które ludzie chcieliby rozwiązać skutecznie, ale dla których nie wydajny algorytm jest znana, takich jak problem spełnialności , do Hamiltona problemu ścieżki i problemu tytułowej wierzchołek . Ponieważ deterministyczne maszyny Turinga są specjalnymi niedeterministycznymi maszynami Turinga, łatwo zauważyć, że każdy problem w P należy również do klasy NP.

Pytanie, czy P równa się NP, jest jednym z najważniejszych otwartych pytań w informatyce teoretycznej ze względu na szerokie implikacje rozwiązania. Jeśli odpowiedź brzmi „tak”, można wykazać, że wiele ważnych problemów ma bardziej efektywne rozwiązania. Należą do nich różnego rodzaju problemy programowania liczb całkowitych w badaniach operacyjnych , wiele problemów w logistyce , przewidywanie struktury białek w biologii oraz umiejętność znajdowania formalnych dowodów twierdzeń z czystej matematyki . Problem P versus NP jest jednym z problemów Nagrody Milenijnej zaproponowanych przez Clay Mathematics Institute . Za rozwiązanie problemu przewidziana jest nagroda w wysokości 1 000 000 USD.

Problemy w NP, o których nie wiadomo, czy są w P lub NP-zupełne

Ladner wykazał, że jeśli P ≠ NP, to w NP występują problemy , które nie są ani w P, ani w NP-zupełne . Takie problemy nazywane są problemami NP-pośrednimi . Problemem wykres Izomorfizm The dyskretnych problemem logarytm i błąd całkowitą faktoryzacji przykłady problemów, uważa się, NP-półproduktu. Są to jedne z nielicznych problemów NP, o których nie wiadomo, czy występują w P lub są NP-zupełne .

Problemem wykres Izomorfizm jest obliczeniowa Problem określenia czy dwa skończonych wykresy są izomorficzne . Ważnym nierozwiązanym problemem w teorii złożoności jest to, czy problem izomorfizmu grafów występuje w P , NP-zupełnym czy NP-pośrednim. Odpowiedź nie jest znana, ale uważa się, że problem nie jest przynajmniej NP-zupełny. Jeśli izomorfizm grafu jest NP-zupełny, wielomianowa hierarchia czasowa zapada się do drugiego poziomu. Ponieważ powszechnie uważa się, że hierarchia wielomianowa nie zapada się do żadnego skończonego poziomu, uważa się, że izomorfizm grafu nie jest NP-zupełny. Najlepszy algorytm dla tego problemu, ze względu na László Babai i Eugene Luks zabrakło czasu na wykresach z n wierzchołków, chociaż niektóre ostatnie prace Babai oferuje kilka potencjalnie nowych perspektyw w tej sprawie. ${\ Displaystyle O (2 ^ {\ sqrt {n \ log n}})}$

Problemem całkowitą faktoryzacji jest obliczeniowa problemu określania czynniki pierwsze danej liczby całkowitej. Sformułowany jako problem decyzyjny, jest to problem decydowania, czy dane wejściowe mają czynnik pierwszy mniejszy niż k . Nie jest znany żaden wydajny algorytm faktoryzacji liczb całkowitych, a fakt ten stanowi podstawę kilku nowoczesnych systemów kryptograficznych, takich jak algorytm RSA . Problem faktoryzacji liczb całkowitych dotyczy NP i współ-NP (a nawet UP i współ-UP). Jeśli problem jest NP-zupełny , wielomianowa hierarchia czasowa zwinie się do pierwszego poziomu (tj. NP będzie równe co-NP ). Najbardziej znanym algorytmem faktoryzacji liczb całkowitych jest ogólne sito pola liczbowego , które wymaga czasu na faktoryzację nieparzystej liczby całkowitej n . Jednak najbardziej znany algorytm kwantowy dla tego problemu, algorytm Shora , działa w czasie wielomianowym. Niestety fakt ten niewiele mówi o tym, gdzie leży problem w odniesieniu do klas niekwantowej złożoności. ${\ Displaystyle O (e ^ {\ lewo ({\ sqrt [{3}] {\ Frac {64} {9}}} \ prawej) {\ sqrt [{3}] {(\ log n)}} \sqrt[{3}]{(\log \log n)^{2}}}})}$

Separacje między innymi klasami złożoności

Podejrzewa się, że wiele znanych klas złożoności jest nierównych, ale nie zostało to udowodnione. Na przykład P ⊆ NP ⊆ PP ⊆ PSPACE , ale możliwe jest , że P = PSPACE . Jeśli P nie jest równe NP , to P również nie jest równe PSPACE . Ponieważ istnieje wiele znanych klas złożoności między P i PSPACE , takich jak RP , BPP , PP , BQP , MA , PH , itp., możliwe jest, że wszystkie te klasy złożoności zostaną zwinięte do jednej klasy. Udowodnienie, że którakolwiek z tych klas jest nierówna, byłoby poważnym przełomem w teorii złożoności.

W podobny sposób, co-NP jest klasą zawierającą problemy z dopełnieniem (tj. problemy z odwróconymi odpowiedziami tak / nie ) problemów NP . Uważa się, że NP nie jest równe co-NP ; jednak nie zostało to jeszcze udowodnione. Jasne jest, że jeśli te dwie klasy złożoności nie są równe, to P nie jest równe NP , ponieważ P = co-P . Zatem jeśli P = NP mielibyśmy co-P = co-NP, skąd NP = P = co-P = co-NP .

Podobnie nie wiadomo, czy L (zbiór wszystkich problemów, które można rozwiązać w przestrzeni logarytmicznej) jest ściśle zawarty w P czy równy P . Ponownie, istnieje wiele klas złożoności między tymi dwoma, takich jak NL i NC , i nie wiadomo, czy są to odrębne, czy równe klasy.

Podejrzewa się, że P i BPP są równe. Jednak obecnie jest otwarty, jeśli BPP = NEXP .

Krnąbrność

Problem, który można rozwiązać teoretycznie (np. mając duże, ale ograniczone zasoby, zwłaszcza czas), ale dla którego w praktyce każde rozwiązanie wymaga zbyt wielu zasobów, aby było użyteczne, jest znany jako problem nierozwiązywalny problem . I odwrotnie, problem, który można rozwiązać w praktyce, nazywa się arozwiązywalny problem , dosłownie „problem, który można rozwiązać”. Termin niewykonalne (dosłownie „nie można zrobić”) jest czasami używane zamiennie z trudny , chociaż ryzyko pomyłki zwykonalnego rozwiązaniawoptymalizacji matematycznej.

Problemy wykonalne są często identyfikowane z problemami, które mają rozwiązania wielomianowe ( P , PTIME ); jest to znane jako teza Cobhama-Edmondsa . Problemy, o których wiadomo, że są nierozwiązywalne w tym sensie, obejmują te, które są trudne w EXPTIME . Jeśli NP nie jest tym samym co P, to problemy NP-trudne również są nierozwiązywalne w tym sensie.

Jednak ta identyfikacja jest niedokładna: rozwiązanie wielomianowe z dużym stopniem lub dużym współczynnikiem wiodącym szybko rośnie i może być niepraktyczne w przypadku praktycznych problemów z wielkością; odwrotnie, rozwiązanie w czasie wykładniczym, które rośnie powoli, może być praktyczne na realistycznych danych wejściowych, lub rozwiązanie, które w najgorszym przypadku zajmuje dużo czasu, może zająć krótki czas w większości przypadków lub w przeciętnym przypadku, a zatem nadal będzie praktyczne. Powiedzenie, że problemu nie ma w P, nie oznacza, że ​​wszystkie duże przypadki problemu są trudne, a nawet, że większość z nich jest trudna. Na przykład okazało się , że problem decyzyjny w arytmetyce Presburgera nie znajduje się w P, ale napisano algorytmy, które w większości przypadków rozwiązują problem w rozsądnym czasie. Podobnie, algorytmy mogą rozwiązywać problem NP-zupełny plecakowy w szerokim zakresie rozmiarów w czasie krótszym niż kwadratowy, a programy do rozwiązywania SAT rutynowo obsługują duże przypadki problemu spełnialności NP-zupełnej Boole'a .

Aby zobaczyć, dlaczego algorytmy czasu wykładniczego są generalnie bezużyteczne w praktyce, rozważ program, który wykonuje 2 ⁿ operacji przed zatrzymaniem. Dla małego n , powiedzmy 100, i zakładając dla przykładu, że komputer wykonuje 10 ¹² operacji na sekundę, program działałby przez około 4 × 10 ¹⁰ lat, czyli ten sam rząd wielkości co wiek wszechświata . Nawet przy znacznie szybszym komputerze program byłby użyteczny tylko w bardzo małych przypadkach iw tym sensie nierozwiązywalność problemu jest w pewnym stopniu niezależna od postępu technologicznego. Jednak algorytm czasu wykładniczego, który wymaga 1,0001 ⁿ operacji, jest praktyczny, dopóki n nie będzie stosunkowo duże.

Podobnie algorytm wielomianowy nie zawsze jest praktyczny. Jeśli jego czas działania wynosi, powiedzmy, n ¹⁵ , nierozsądnie jest uważać go za wydajny i nadal jest bezużyteczny, z wyjątkiem małych przypadków. Rzeczywiście, w praktyce nawet n ³ lub n ² algorytmów jest często niepraktycznych przy realistycznych rozmiarach problemów.

Teoria ciągłej złożoności

Teoria ciągłej złożoności może odnosić się do teorii złożoności problemów, które obejmują funkcje ciągłe, które są aproksymowane przez dyskretyzacje, jak badano w analizie numerycznej . Jednym z podejść do teorii złożoności analizy numerycznej jest złożoność oparta na informacji .

Teoria ciągłej złożoności może również odnosić się do teorii złożoności wykorzystującej obliczenia analogowe , która wykorzystuje ciągłe układy dynamiczne i równania różniczkowe . Teorię sterowania można uznać za formę obliczeń, a równania różniczkowe są wykorzystywane w modelowaniu układów czasu ciągłego i hybrydowych układów dyskretno-ciągłych w czasie.

Historia

Wczesnym przykładem analizy złożoności algorytmu jest analiza czasu wykonania algorytmu euklidesowego wykonana przez Gabriela Lamé w 1844 roku.

Zanim rozpoczęły się faktyczne badania, wprost poświęcone złożoności problemów algorytmicznych, różni badacze położyli liczne podwaliny. Wśród nich największy wpływ miała definicja maszyn Turinga Alana Turinga z 1936 roku, która okazała się bardzo solidnym i elastycznym uproszczeniem komputera.

Początek systematycznych badań nad złożonością obliczeniową przypisuje się przełomowemu artykułowi „O złożoności obliczeniowej algorytmów” Jurisa Hartmanisa i Richarda E. Stearnsa z 1965 r. , który przedstawił definicje złożoności czasowej i złożoności przestrzennej oraz udowodnił twierdzenia o hierarchii. Ponadto w 1965 roku Edmonds zasugerował, aby uznać „dobry” algorytm za taki, którego czas działania jest ograniczony wielomianem wielkości wejściowej.

Wcześniejsze artykuły badające problemy rozwiązywalne przez maszyny Turinga o określonych zasobach ograniczonych obejmują definicję automatów liniowo ograniczonych Johna Myhilla (Myhill 1960), studium Raymonda Smullyana o zbiorach elementarnych (1961), a także artykuł Hisao Yamady o rzeczywistych obliczenia czasu (1962). Nieco wcześniej Boris Trakhtenbrot (1956), pionier w tej dziedzinie z ZSRR, badał inny specyficzny miernik złożoności. Jak wspomina:

Jednak [moje] początkowe zainteresowanie [teorią automatów] było coraz bardziej odkładane na bok na rzecz złożoności obliczeniowej, ekscytującego połączenia metod kombinatorycznych, odziedziczonych po teorii przełączania , z arsenałem pojęciowym teorii algorytmów. Te pomysły przyszły mi do głowy już w 1955 roku, kiedy ukułem termin „funkcja sygnalizująca”, który jest obecnie powszechnie znany jako „miara złożoności”.

W 1967 roku Manuel Blum sformułował zbiór aksjomatów (obecnie znanych jako aksjomaty Bluma ) określających pożądane własności miar złożoności na zbiorze funkcji obliczalnych i dowiódł ważnego wyniku, tzw. twierdzenia o przyśpieszeniu . Dziedzina ta zaczęła się rozwijać w 1971 roku, kiedy Stephen Cook i Leonid Levin udowodnili istnienie praktycznie istotnych problemów, które są NP-zupełne . W 1972 r. Richard Karp wykonał krok naprzód w swoim przełomowym artykule „Reducibility Among Combinatorial Problems”, w którym wykazał, że 21 różnych kombinatorycznych i grafowych problemów teoretycznych , z których każdy słynie z nierozwiązywalności obliczeniowej, jest NP-zupełnych.

Zobacz też

Działa na złożoność

• Wuppuluri, Shyam; Doria, Francisco A., wyd. (2020), Unraveling Complexity: The Life and Work of Gregory Chaitin , World Scientific, doi : 10.1142/11270 , ISBN 978-981-12-0006-9

Bibliografia

Cytaty

Podręczniki

• Arora, Sanjeev ; Barak, Boaz (2009), Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press, ISBN 978-0-521-42426-4, Zbl  1193.68112
• Downey, Rod; Stypendyści, Michael (1999), sparametryzowana złożoność , Monografie informatyki, Berlin, New York: Springer-Verlag, ISBN 9780387948836
• Du, Ding-Zhu; Ko, Ker-I (2000), Teoria złożoności obliczeniowej , John Wiley & Sons, ISBN 978-0-471-34506-0
• Garey, Michael R .; Johnson, David S. (1979) Komputery i krnąbrność: Przewodnik do teorii Problem NP-zupełny , W. H. Freeman , ISBN 0-7167-1045-5
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press
• van Leeuwen, Jan , wyd. (1990), Podręcznik informatyki teoretycznej (tom A): algorytmy i złożoność , MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), złożoność obliczeniowa (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7
• Sipser, Michael (2006), Wprowadzenie do teorii obliczeń (2nd ed.), USA: Thomson Course Technology, ISBN 978-0-534-95097-2

Ankiety

• Khalil, Hatem; Ulery, Dana (1976), "Przegląd aktualnych badań nad złożonością algorytmów dla równań różniczkowych cząstkowych" , Proceedings of the Annual Conference on - ACM 76 , ACM '76: 197-201, doi : 10.1145/800191.805573 , S2CID  15497394
• Cook, Stephen (1983), „Przegląd złożoności obliczeniowej”, Commun. ACM , 26 (6): 400–408, doi : 10.1145/358141.358144 , ISSN  0001-0782 , S2CID  14323396
• Fortnow, Lanca; Homer, Steven (2003), "Krótka historia złożoności obliczeniowej" (PDF) , Biuletyn EATCS , 80 : 95-133
• Mertens, Stephan (2002), "Złożoność obliczeniowa dla fizyków", Computing in Science and Eng. , 4 (3): 31–47, arXiv : cond-mat/0012185 , Bibcode : 2002CSE.....4c..31M , doi : 10.1109/5992.998639 , ISSN  1521-9615 , S2CID  633346

Linki zewnętrzne

• Złożoność Zoo
• „Klasy złożoności obliczeniowej” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Jakie są najważniejsze wyniki (i artykuły) w teorii złożoności, które każdy powinien znać?
• Scott Aaronson: Dlaczego filozofowie powinni dbać o złożoność obliczeniową