Problem NP-zupełny

W teorii złożoności An NP-zupełny problemu lub NPC błąd (to znaczy pełne problemem dla NP klasy ) jest problem decyzyjny weryfikacji następujące właściwości:

możliwa jest sprawna weryfikacja rozwiązania (w czasie wielomianowym ); klasę problemów weryfikujących tę właściwość oznaczono jako NP;
wszystkie problemy klasy NP sprowadzają się do tej poprzez redukcję wielomianową ; oznacza to, że problem jest co najmniej tak trudny, jak wszystkie inne problemy klasy NP.

NP-trudny problem, to problem, który spełnia drugi warunek, a zatem mogą być w większej klasie problemu i dlatego trudniej niż klasy NP.

Chociaż można szybko zweryfikować proponowane rozwiązanie problemu NP-zupełnego, nie wiadomo, jak je skutecznie znaleźć . Tak jest na przykład w przypadku problemu komiwojażera lub problemu z plecakiem .

Wszystkie algorytmy znane z rozwiązywania problemów NP-zupełnych mają wykładniczy czas wykonania danych wejściowych w najgorszym przypadku i dlatego są w praktyce bezużyteczne dla instancji o średniej wielkości.

Druga właściwość definicji oznacza, że jeśli istnieje algorytm wielomianowy do rozwiązania któregokolwiek z problemów NP-zupełnych, to wszystkie problemy klasy NP można rozwiązać w czasie wielomianowym. Znalezienie algorytmu wielomianu dla problemu NP-zupełnego lub udowodnienie, że nie istnieje, pozwoliłoby nam dowiedzieć się, czy P = NP czy P ≠ NP, pytanie otwarte, które jest jednym z najważniejszych nierozwiązanych dotychczas problemów matematycznych .

W praktyce specjaliści IT i programiści często napotykają problemy NP-zupełne. W tym przypadku świadomość, że problem, nad którym pracujemy, jest NP-zupełny, jest wskazówką, że problem jest trudny do rozwiązania, dlatego lepiej szukać rozwiązań przybliżonych za pomocą algorytmów aproksymacyjnych lub stosować heurystykę do znalezienia dokładnych rozwiązań.

Definicja formalna

Problem decyzyjny można opisać matematycznie przez formalnego języka , słowa, które odpowiadają instancji problemu, dla których odpowiedź brzmi tak . Bez utraty ogólności możemy założyć, że wszystkie rozważane przez nas języki są zdefiniowane w tym samym alfabecie . $\ Sigma$

W definicji NP-kompletności zaangażowane są dwie klasy złożoności, przedstawione bardziej szczegółowo w teorii złożoności :

Klasa jest zbiorem języków rozstrzygalnych w czasie wielomianowym przez niedeterministyczną maszynę Turinga . $NP \,$
Klasa jest zbiorem języków rozstrzygalnych w czasie wielomianowym przez deterministyczną maszynę Turinga . Jest zawarty w . $P \,$ $NP \,$

Język jest NP-trudne jeśli istnieje wielomian zmniejszenie jakiegokolwiek języka na , to znaczy funkcja (gdzie jest alfabet z tych języków), obliczalna w czasie wielomianowym na deterministycznej maszyny Turinga, takich jak niż: $L \,$ $\ In NP \,$ $L \,$ $f: \ Sigma ^ {*} \ mapsto \ Sigma ^ {*} \,$ $\ Sigma \,$

\ forall w \ in \ Sigma ^ {*}, w \ in L '\ Leftrightarrow f (w) \ in L \,

Jeśli więcej , język jest NP-kompletny . $L \ in NP \,$ $L \,$

Podano klasę języków NP-pełnych . $NPC \,$

Mówimy, że problem decyzyjny jest „NP-zupełny”, gdy odpowiedni język jest NP-zupełny. Jest to pojęcie nieformalne, ponieważ istnieje kilka sposobów kodowania przypadków problemu, ale nie stwarza to żadnych trudności, o ile stosuje się rozsądne zakodowanie problemu w rozważanym języku (patrz sekcja NP-słaba kompletność ).

Nadużywanie języka często kwalifikuje się jako problemy optymalizacyjne „NP-zupełne” , a nie problemy decyzyjne. Zatem powiemy, że problem komiwojażera polegający na znalezieniu krótszego obwodu przechodzącego tylko raz przez każdy z wierzchołków skończonego grafu połączonego jest -kompletny. Jest to uzasadnione tym, że każdy problem optymalizacyjny możemy przekształcić w problem decyzyjny i odwrotnie (patrz rozdział „ Od istnienia do decyzji ” w artykule o teorii złożoności). $NP$

Historia

Pojęcie NP-zupełności zostało wprowadzone w 1971 r. Przez Stephena Cooka w artykule zatytułowanym Złożoność procedur dowodzenia twierdzeń , chociaż słowo „NP-zupełne” nie pojawia się wprost w artykule. Na konferencji, na której został zaprezentowany, toczyła się gorąca dyskusja wśród obecnych naukowców na temat tego, czy problemy NP-zupełne można rozwiązać w czasie wielomianowym na deterministycznej maszynie Turinga . John Hopcroft ostatecznie przekonał uczestników, że kwestia musi zostać odroczona, ponieważ nikt nie zdołał udowodnić ani zaprzeczyć wynikowi.

Kwestia czy P = NP nie jest jeszcze rozwiązany. Jest to część Millennium Prize Problems , zestawu siedmiu problemów, za które Clay Institute of Mathematics oferuje nagrodę w wysokości miliona dolarów . Wystarczyłoby znaleźć pojedynczy problem NP, który jest zarówno NP-zupełny, jak i P, aby udowodnić tę hipotezę, lub wykazać pojedynczy problem NP, który nie jest w P, aby udowodnić jego zaprzeczenie.

Wynik pracy Cooka, niezależnie zademonstrowany przez Leonida Levina w ZSRR, jest obecnie znany jako twierdzenie Cooka-Levina . To twierdzenie stwierdza, że istnieje problem NP-zupełny. Cook wybrał problem SAT, a Levin - problem teselacji. W 1972 roku Richard Karp udowodnił kompletność NP kilku innych fundamentalnych i bardzo odmiennych problemów komputerowych, znanych jako lista 21 problemów NP-zupełnych Karpa . Od tego czasu wykazano NP-kompletność tysięcy innych problemów.

Dowody kompletności NP

Aby zademonstrować NP-zupełność nowego problemu , zwykłą metodą jest znalezienie znanego już problemu NP-zupełnego, który sprowadza się do . To wystarczy, aby pokazać, że jest NP-kompletny. Rzeczywiście, dla wszystkiego mamy Π ≤ P Π 2 ≤ P Π 1 (zależność redukcji wielomianu ≤ P jest przechodnia). ${\ displaystyle \ Pi _ {1} \ w NP}$ $\ Pi _ {2}$ $\ Pi _ {1}$ $\ Pi _ {1}$ ${\ displaystyle \ Pi \ w NP}$

Aby zilustrować tę metodę, oto demonstracja NP-zupełności całkowitej optymalizacji liniowej (OLNE) przez redukcję z SAT , która jest NP-zupełna, jak wyjaśniono powyżej.

OLNE służy do określenia, czy układ nierówności liniowych ma co najmniej jedno rozwiązanie całkowite.

Przykład 2y ≥ 1, 2y - 4x ≤ 1, 2y + 4x ≤ 6 ma rozwiązanie całkowite (x = 1, y = 1); 2y ≥ 1, 2y - 4x ≤ 1, 2y + 4x ≤ 5 nie ma rozwiązania całkowitego.

SAT polega na określeniu, czy formuła logiczna w postaci normalnej koniunkcji jest zadowalająca.

Przykład

(v_ {1} \ lor v_ {2}) \ land (v_ {1} \ lor \ lnot v_ {2}) \ land (\ lnot v_ {1} \ lor \ lnot v_ {2})

można spełnić, ustawiając v 1 = prawda i v 2 = fałsz.

(v_ {1} \ lor v_ {2}) \ land (v_ {1} \ lor \ lnot v_ {2}) \ land (\ lnot v_ {1})

nie jest satysfakcjonująca.

Problem OLNE jest rzeczywiście problemem NP: sprawdzenie, czy przypisanie zmiennych jest rozwiązaniem, jest osiągalne w efektywny sposób. Definiujemy funkcję redukcji f w następujący sposób. Rozważ wzór w postaci normalnej koniunkcji. Jeden definiuje się jako następujący problem OLNE: $\ phi$ $f (\ phi)$

Każdej zmiennej v i odpowiada zmienna x i systemu. Dodatkowo dodajemy do systemu ograniczenie 0 ≤ x i ≤ 1.
Dla każdej klauzuli formularza ze zmiennymi, które niekoniecznie są odrębne, ograniczenie jest dodawane do systemu . $v_ {1} \ lor \ dots \ lor v_ {k} \ lor \ lnot v _ {{k + 1}} \ lor \ dots \ lor \ lnot v_ {n}$ $v_ {1}, \ dots, v_ {n}$ $x_ {1} + \ dots + x_ {k} + (1-x _ {{k + 1}}) + \ dots + (1-x_ {n}) \ geq 1$

Przykład Dla wzoru układ liniowy zawiera pięć nierówności:

(v_ {1} \ lor v_ {2}) \ land (v_ {1} \ lor \ lnot v_ {2}) \ land (\ lnot v_ {1} \ lor \ lnot v_ {2})

0 ≤ x 1 ≤ 1, 0 ≤ x 2 ≤ 1, x 1 + x 2 ≥ 1, x 1 + (1 - x 2 ) ≥ 1 i (1 - x 1 ) + (1 - x 2 ) ≥ 1.

Widzimy wtedy, że jeśli jest satysfakcjonujące, to ustawiając: $\ phi$

x i = 0 jeśli v i = fałsz,
x i = 1, jeśli v i = prawda,

uzyskuje się rozwiązanie problemu OLNE. I odwrotnie, jeśli problem OLNE ma rozwiązanie, to wzór można spełnić, ustawiając zmienne v i tak, że x i = 1. Tak więc funkcja f jest rzeczywiście redukcją SAT w OLNE. Ponadto f jest obliczalne w czasie wielomianowym, więc OLNE jest problemem NP-zupełnym.

Lista problemów NP-zupełnych

Niektóre znaczące problemy NP-zupełne obejmują:

SAT i jego wariant 3-SAT ;
Hamiltonian Problem cyklu i jego wariant ważona The podróżowanie sprzedawca problemem ;
kliknięcie maksymalna (odpowiednik maksymalnie równomierny i szczyty pokrywa minimalnych );
minimalny problem zbioru dominującego ;
problemy z kolorowaniem wykresów ;
problem z plecakiem .

Należy zauważyć, że mówienie o problemie NP w przypadku niektórych z tych problemów jest więc nadużyciem językowym, ponieważ nie są to problemy decyzyjne . Jednak problemy decyzyjne związane z problemem optymalizacji, zazwyczaj w postaci: „czy istnieje rozwiązanie kosztujące mniej niż…?” », Czy są dobrze NP-kompletne.

Diagram po prawej stronie wskazuje, w przypadku niektórych z tych problemów, w jakiej kolejności generalnie dowodzimy NP-kompletności. Należy zauważyć, że ta kolejność redukcji nie jest jedyną możliwą, ponieważ z definicji zawsze istnieje redukcja między dowolnymi dwoma problemami NP-zupełnymi. Jego celem jest uproszczenie demonstracji.

Kontrprzykłady

Czasami pozornie niewielka zmiana zamienia problem NP-zupełny w problem klasy P. Kilka przykładów:

3-SAT, ograniczenie SAT w przypadku, gdy wszystkie klauzule mają co najwyżej trzy zmienne, jest NP-zupełne, podczas gdy 2-SAT można zdecydować w czasie liniowym;
problem kolorowania wykresów jest NP-kompletny z trzema kolorami, ale wielomian z dwoma kolorami;
wiedząc, czy istnieje obwód hamiltonowski, jest NP-zupełna, wiedząc, czy istnieje obwód Eulera w P.

Zakłada się, że niektóre problemy w NP, na przykład te wykorzystywane w kryptografii klucza publicznego , są ściśle związane z P i NPC. W szczególności metoda RSA opiera się na trudności z faktoryzacją liczb całkowitych . Żaden algorytm wielomianowy nie jest znany, aby go rozwiązać, ale problem należy do NP co-NP i dlatego prawdopodobnie nie jest NP-zupełny. $\ czapka$

Z drugiej strony istnieją trudniejsze problemy decyzyjne niż problemy NP-zupełne. Niektóre problemy są nierozstrzygalne , na przykład problem z zamykaniem . Niektóre problemy rozstrzygalne wymagają spacji wykładniczej i dlatego nie są w NP, na przykład porównanie języków oznaczonych dwoma wyrażeniami regularnymi, w których jeden dopuszcza, oprócz zwykłych operacji, operację kwadratową (jest to kompletny problem w EXPSPACE ).

Rozkład

Dokładne metody

NP-kompletność tylko daje wyobrażenie o trudności problemu w najgorszym przypadku. Innymi słowy, nawet jeśli nie wiemy, jak szybko rozwiązać wszystkie przypadki problemu NP-zupełnego, czasami jest to możliwe w przypadku niektórych z nich.

W związku z tym algorytmy rozdzielania i oceny nie wielomianowe mogą mieć rozsądny czas wykonania dla stosunkowo dużych wystąpień.

Jeśli trzeba rozwiązać tylko podklasę możliwych instancji, problem może stać się łatwy. Na przykład poszukiwanie maksymalnego niezależnego (NP-zupełnego) jest możliwe w czasie wielomianowym na grafach dwudzielnych lub innych rodzinach grafów.

W niektórych przypadkach wiemy, jak pokazać, że przypadkowe przypadki problemu NP-zupełnego są łatwe. Na przykład :

Kolorowanie wykresu za pomocą k kolorów ( k ≥ 3) jest NP-całkowite, ale trudne przypadki odpowiadają rzadkim wykresom. Zatem, jeśli losowo wybierzemy graf z n wierzchołkami, równomiernie spośród 2 n (n-1) / 2 możliwych, prawdopodobieństwo istnienia k- zabarwienia zmierza do 0, gdy n wzrośnie. Ponadto algorytm chciwego kolorowania , eksplorujący wierzchołki w dowolnej kolejności, kończy się średnio po zbadaniu O (1) wierzchołków;
W przeciwieństwie do tego losowy wykres zawiera obwód hamiltonianu z prawdopodobieństwem dążącym do 1, gdy jego rozmiar dąży do nieskończoności , a taki obwód można znaleźć w wielomianowym czasie probabilistycznym.

Wreszcie podejście do sparametryzowanej złożoności polega na zidentyfikowaniu parametru, który, jeśli pozostaje mały, umożliwia szybkie rozwiązanie problemu. Zwłaszcza algorytmy FPT w parametrze k rozwiązują problem w czasie proporcjonalnym do iloczynu dowolnej funkcji k i wielomianu wielkości instancji, co zapewnia algorytm wielomianu, gdy k jest ustalone.

Przybliżone metody

Gdy dokładne metody rozwiązywania nie mają zastosowania, algorytmy aproksymacyjne (lub w przypadku ich braku heurystyki ) umożliwiają znalezienie rozwiązań przybliżających optymalne w rozsądnym czasie dla pewnej liczby problemów NP-zupełnych.

Niektórych problemów nie da się przybliżyć, takich jak problem komiwojażera .
Z drugiej strony problem komiwojażera ograniczony do przypadku, w którym odległości spełniają trójkątną nierówność, można przybliżyć współczynnikiem 3/2: istnieje algorytm wielomianowy, który oblicza ścieżkę, której długość jest co najwyżej 3/2 razy większa niż ścieżka optymalna.
Inne problemy dopuszczają wielomianowy schemat aproksymacji , tj. Można je aproksymować do współczynnika (1 + ε) w czasie wielomianu dla wszystkich ε> 0. Tak jest w przypadku problemu worka z powrotem .

Słaba NP-kompletność

Jak wspomniano powyżej, istnieje kilka sposobów kodowania przypadków problemu w postaci słów (składających się z skończonej serii symboli określonego i skończonego alfabetu). Wybór szczególnie długiego kodowania w sztuczny sposób zmniejsza złożoność problemu, ponieważ jest on wyrażany jako funkcja rozmiaru danych wejściowych.

W szczególności liczba całkowita n może być zakodowana na log 2 n symbolach, jeśli jest zapisana na podstawie 2 (lub wyższej), ale zajmuje n symboli, jeśli jest zapisana w jednostce jednoargumentowej , która jest wykładniczo większa.

Problemy, które można rozwiązać w czasie wielomianowym, gdy ich dane wejściowe są kodowane jednoargumentowo, nazywane są problemami „słabego NP-zupełnego”. Do tej kategorii zalicza się problem plecaka i jego warianty. Rzeczywiście, można je rozwiązać przez programowanie dynamiczne w czasie wielomianowym w liczbie obiektów i największej ilości interweniującej we wpisie.

W przeciwieństwie do tego, problemy, które w tym przypadku pozostają NP-zupełne, są uważane za silne . Tak jest w przypadku większości innych problemów wymienionych w tym artykule, takich jak SAT, CLICK, kolorowanie wykresów itp.

Uwagi i odniesienia

Stephen Cook , The złożoność procedur dowodzenia twierdzeń , Proceedings of the Third Annual ACM Symposium on Theory of Computing, strony 151–158, 1971.
W tym czasie wymiana naukowa między światem zachodnim a ZSRR była bardzo słaba.
Aby być precyzyjnym, rozmiar rozwiązania musi być wielomianowo ograniczony do rozmiaru wejścia, co jest zawsze możliwe tutaj.
Albert R. Meyer i Larry Stockmeyer , Problem równoważności dla wyrażeń regularnych z kwadratem wymaga przestrzeni wykładniczej , 13. Sympozjum IEEE na temat przełączania i teorii automatów , październik 1972, s. 125-129.
Demonstracja zawarta jest w cytowanej powyżej pracy Wilfa.
Jean-Paul Delahaye , Inteligencja i obliczenia, Belin - Pour la Science, 2002, ( ISBN 2-84245-040-X ) (rozdział 1, „Prawa wszystko albo nic”).
D. Angluin i LG Valiant, Szybkie algorytmy probabilistyczne dla obwodów hamiltonowskich i dopasowań , Journal of Computer and System Sciences , tom 18, wydanie 2, str. 155-193,1979.

Zobacz też

Powiązane artykuły

Linki zewnętrzne

(en) Wersja online książki „ Algorytmy i złożoność” Herberta S. Wilfa (zawiera rozdział poświęcony problemom NP-zupełnym).
(en) Kompendium problemów optymalizacji NP .
(nie) Klasa NPC w ZOO Złożoności