NP (złożoność) - NP (complexity)

Diagram Eulera dla P , NP, NP-zupełnego i NP-trudnego zbioru problemów. Przy założeniu, że P≠NP, istnienie problemów w obrębie NP, ale poza nimi zarówno P, jak i NP-zupełne, zostało ustalone przez Ladnera .

W teorii złożoności obliczeniowej , NP ( niedeterministyczny czas wielomian ) to klasa złożoności stosowany do klasyfikowania problemów decyzyjnych . NP to zbiór problemów decyzyjnych, dla których instancje problemowe , gdzie odpowiedź brzmi „tak”, mają dowody weryfikowalne w czasie wielomianowym przez deterministyczną maszynę Turinga lub alternatywnie zbiór problemów, które mogą być rozwiązane w czasie wielomianowym przez niedeterministyczną maszynę Turinga maszyna .

Równoważną definicją NP jest zbiór problemów decyzyjnych rozwiązywanych w czasie wielomianowym przez niedeterministyczną maszynę Turinga . Definicja ta jest podstawą skrótu NP; „ niedeterministyczny , wielomianowy czas”. Te dwie definicje są równoważne, ponieważ algorytm oparty na maszynie Turinga składa się z dwóch faz, z których pierwsza składa się z odgadnięcia rozwiązania, które jest generowane w sposób niedeterministyczny, natomiast druga faza składa się z algorytmu deterministycznego, który weryfikuje, czy domysł jest rozwiązaniem problemu.

Łatwo zauważyć, że klasa złożoności P (wszystkie problemy rozwiązywalne deterministycznie w czasie wielomianowym) jest zawarta w NP (problemy, w których rozwiązania można zweryfikować w czasie wielomianowym), ponieważ jeśli problem jest rozwiązywalny w czasie wielomianowym, to rozwiązanie jest również weryfikowalne w czasie wielomianowym, po prostu rozwiązując problem. Ale NP zawiera o wiele więcej problemów, z których najtrudniejsze to problemy NP-zupełne . Algorytm rozwiązujący taki problem w czasie wielomianowym jest również w stanie rozwiązać dowolny inny problem NP w czasie wielomianowym. Najważniejszy problem P versus NP („P = NP?”) to pytanie, czy istnieją algorytmy czasu wielomianowego do rozwiązywania NP-zupełnych i w konsekwencji wszystkich problemów NP. Powszechnie uważa się, że tak nie jest.

Klasa złożoności NP jest powiązana z klasą złożoności co-NP, dla której odpowiedź „nie” można zweryfikować w czasie wielomianowym. To, czy NP = współ-NP, to kolejne nierozstrzygnięte pytanie w teorii złożoności.

Formalna definicja

Klasę złożoności NP można zdefiniować w kategoriach NTIME w następujący sposób:

${\ Displaystyle {\ mathsf {NP}} = \ bigcup _ {k \ w \ mathbb {N}} {\ mathsf {NTIME}} (n ^ {k}).}$

gdzie jest zbiór problemów decyzyjnych, które mogą być rozwiązane przez niedeterministyczną maszynę Turinga w czasie. ${\ Displaystyle {\ mathsf {NTIME}} (n ^ {k})}$${\ Displaystyle O (n ^ {k})}$

Alternatywnie, NP można zdefiniować za pomocą deterministycznych maszyn Turinga jako weryfikatorów. Język L w NP, wtedy i tylko wtedy, gdy istnieją wielomiany p i q oraz deterministycznej maszyny Turinga M , tak że

• Dla wszystkich x i y maszyna M działa w czasie p (| x |) na wejściu${\displaystyle (x,y)}$
• Dla wszystkich x w L , istnieje łańcuch y o długości q (| x |) taki, że${\ Displaystyle M (x, y) = 1}$
• Dla wszystkich x spoza L i wszystkich ciągów y o długości q (| x |),${\ Displaystyle M (x, y) = 0}$

Tło

W NP zawiera się wiele problemów informatycznych , podobnie jak wersje decyzyjne wielu problemów wyszukiwania i optymalizacji.

Definicja oparta na weryfikatorze

Aby wyjaśnić definicję NP opartą na weryfikatorach, rozważmy problem sumy podzbiorów : Załóżmy, że mamy dane liczb całkowitych {−7, −3, −2, 5, 8} i chcemy wiedzieć, czy niektóre z nich liczby całkowite sumują się do zera. Tutaj odpowiedź brzmi „tak”, ponieważ liczby całkowite {−3, −2, 5} odpowiadają sumie (−3) + (−2) + 5 = 0. Zadanie rozstrzygnięcia, czy taki podzbiór o sumie zerowej istnieje nazywa się problemem sumy podzbiorów .

Aby odpowiedzieć, czy niektóre liczby całkowite dodają się do zera, możemy stworzyć algorytm, który uzyska wszystkie możliwe podzbiory. Wraz ze wzrostem liczby liczb całkowitych, które wprowadzamy do algorytmu, zarówno liczba podzbiorów, jak i czas obliczeń rośnie wykładniczo.

Zauważ jednak, że jeśli otrzymamy konkretny podzbiór, możemy skutecznie zweryfikować, czy suma podzbioru wynosi zero, sumując liczby całkowite z podzbioru. Jeśli suma wynosi zero, ten podzbiór jest dowodem lub świadkiem, że odpowiedź brzmi „tak”. Weryfikatorem jest algorytm sprawdzający, czy dany podzbiór ma sumę zero . Oczywiście, sumowanie liczb całkowitych podzbioru można wykonać w czasie wielomianowym, a problem sumy podzbioru jest zatem w NP.

Powyższy przykład można uogólnić na dowolny problem decyzyjny. Biorąc pod uwagę dowolny przypadek I problemu i świadka W, jeśli istnieje weryfikator V tak, że biorąc pod uwagę uporządkowaną parę (I, W) jako dane wejściowe, V zwraca „tak” w czasie wielomianowym, jeśli świadek udowodni, że odpowiedź brzmi „tak” lub "nie" w czasie wielomianowym inaczej, to jest w NP. ${\ Displaystyle \ Pi}$${\ Displaystyle \ Pi}$

Wersja "nie"-odpowiedź tego problemu jest sformułowana jako: "przy skończonym zbiorze liczb całkowitych, czy każdy niepusty podzbiór ma sumę niezerową?". Definicja NP oparta na weryfikatorze nie wymaga wydajnego weryfikatora dla odpowiedzi „nie”. Klasa problemów z takimi weryfikatorami dla odpowiedzi „nie” nazywa się co-NP. W rzeczywistości pytaniem otwartym jest, czy wszystkie problemy w NP mają również weryfikatory dla odpowiedzi „nie”, a zatem są współistniejące z NP.

W niektórych publikacjach weryfikator jest nazywany „certyfikatorem”, a świadek „ certyfikatem ”.

Definicja maszyny

Odpowiednikiem definicji opartej na weryfikatorze jest następująca charakterystyka: NP jest klasą problemów decyzyjnych rozwiązywanych przez niedeterministyczną maszynę Turinga, która działa w czasie wielomianowym . Innymi słowy, problem decyzyjny występuje w NP zawsze, gdy jest rozpoznawany przez jakąś niedeterministyczną maszynę Turinga w czasie wielomianowym z egzystencjalnym warunkiem akceptacji , co oznacza, że wtedy i tylko wtedy, gdy jakaś ścieżka obliczeniowa prowadzi do stanu akceptacji. Ta definicja jest równoważna definicji opartej na weryfikatorze, ponieważ niedeterministyczna maszyna Turinga może rozwiązać problem NP w czasie wielomianowym przez niedeterministyczny wybór certyfikatu i uruchomienie weryfikatora na certyfikacie. Podobnie, jeśli taka maszyna istnieje, to w naturalny sposób można z niej skonstruować wielomianowy weryfikator czasu. ${\ Displaystyle \ Pi}$${\ Displaystyle \ Pi}$${\ Displaystyle M}$${\ Displaystyle w \ w \ Pi}$${\ Displaystyle M(w)}$

W tym świetle możemy zdefiniować co-NP podwójnie jako klasę problemów decyzyjnych rozpoznawanych przez niedeterministyczne maszyny Turinga w czasie wielomianowym z egzystencjalnym warunkiem odrzucenia. Ponieważ egzystencjalny warunek odrzucenia jest dokładnie tym samym, co warunek uniwersalnej akceptacji , możemy rozumieć pytanie NP kontra współ-NP jako pytanie, czy egzystencjalne i uniwersalne warunki akceptacji mają taką samą moc ekspresyjną dla klasy wielomianowego niedeterministycznego Turinga maszyny.

Nieruchomości

NP jest zamknięta w ramach sumy , przecięcia , konkatenacji , gwiazdy Kleene i odwrócenia . Nie wiadomo, czy NP jest zamknięte pod dopełnieniem (pytanie to jest tak zwane pytanie „NP kontra co-NP”)

Dlaczego niektóre problemy z NP są trudne do rozwiązania

Ze względu na wiele ważnych problemów w tej klasie, podjęto szeroko zakrojone wysiłki w celu znalezienia algorytmów wielomianowych dla problemów w NP. Jednak pozostaje wiele problemów w NP, które przeciwstawiają się takim próbom i wydaje się, że wymagają czasu superwielomianowego . To, czy te problemy nie są rozstrzygalne w czasie wielomianowym, jest jednym z największych otwartych pytań w informatyce (patrz problem P versus NP („P=NP”), aby uzyskać dogłębną dyskusję).

Ważnym pojęciem w tym kontekście jest zbiór NP-zupełnych problemów decyzyjnych, który jest podzbiorem NP i może być nieformalnie opisany jako „najtrudniejsze” problemy w NP. Jeśli istnieje algorytm wielomianowy dla choćby jednego z nich, to istnieje algorytm wielomianowy dla wszystkich problemów w NP. Z tego powodu, a także dlatego, że specjalistyczne badania nie pozwoliły na znalezienie algorytmu wielomianowego dla jakiegokolwiek problemu NP-zupełnego, po udowodnieniu, że problem jest NP-zupełny, jest to powszechnie uważane za znak, że algorytm wielomianowy dla tego problemu jest mało prawdopodobny istnieć.

Jednak w praktycznych zastosowaniach, zamiast wydawać zasoby obliczeniowe na poszukiwanie optymalnego rozwiązania, często można znaleźć wystarczająco dobre (ale potencjalnie nieoptymalne) rozwiązanie w czasie wielomianowym. Również rzeczywiste zastosowania niektórych problemów są łatwiejsze niż ich teoretyczne odpowiedniki.

Równoważność definicji

Dwie definicje NP jako klasy problemów rozwiązywalnych przez niedeterministyczną maszynę Turinga (TM) w czasie wielomianowym i klasy problemów sprawdzalnych przez deterministyczną maszynę Turinga w czasie wielomianowym są równoważne. Dowód jest opisany w wielu podręcznikach, na przykład we Wstępie do teorii obliczeń Sipsera , rozdział 7.3.

Aby to pokazać, najpierw załóżmy, że mamy deterministyczny weryfikator. Maszyna niedeterministyczna może po prostu niedeterministycznie uruchomić weryfikator na wszystkich możliwych ciągach dowodu (wymaga to tylko wielomianowo wielu kroków, ponieważ może niedeterministycznie wybrać następny znak w ciągu dowodu w każdym kroku, a długość ciągu dowodu musi być ograniczona wielomianem). Jeśli jakikolwiek dowód jest słuszny, jakaś ścieżka zaakceptuje; jeśli żaden dowód nie jest ważny, ciąg nie jest w języku i zostanie odrzucony.

I odwrotnie, załóżmy, że mamy niedeterministyczną TM o nazwie A, przyjmującą dany język L. W każdym z jego wielomianowo wielu etapów drzewo obliczeniowe maszyny rozgałęzia się co najwyżej w skończonej liczbie kierunków. Musi istnieć co najmniej jedna ścieżka akceptacji, a łańcuch opisujący tę ścieżkę jest dowodem dostarczonym do weryfikatora. Weryfikator może następnie deterministycznie zasymulować A, podążając tylko ścieżką akceptacji i weryfikując, czy akceptuje na końcu. Jeśli A odrzuci dane wejściowe, nie ma ścieżki akceptacji, a weryfikator zawsze odrzuci.

Stosunek do innych klas

NP zawiera wszystkie problemy w P , ponieważ każdy przypadek problemu można zweryfikować, po prostu ignorując dowód i go rozwiązując. NP jest zawarty w PSPACE — aby to pokazać, wystarczy skonstruować maszynę PSPACE, która zapętla wszystkie łańcuchy dowodowe i przekazuje każdy z nich do weryfikatora wielomianowego. Ponieważ maszyna czasu wielomianowego może odczytywać tylko wielomianowo wiele bitów, nie może używać więcej niż przestrzeni wielomianowej, ani nie może odczytać łańcucha dowodowego zajmującego więcej niż przestrzeń wielomianową (więc nie musimy rozważać dowodów dłuższych niż ta). NP jest również zawarte w EXPTIME , ponieważ ten sam algorytm działa w czasie wykładniczym.

co-NP zawiera te problemy, które mają prosty dowód na brak instancji, czasami nazywane kontrprzykładami. Na przykład, testowanie pierwszości leży w trywialny sposób na co-NP, ponieważ można obalić pierwszorzędność liczby całkowitej, po prostu dostarczając nietrywialny czynnik. NP i co-NP tworzą razem pierwszy poziom w hierarchii wielomianowej , wyższy tylko niż P.

NP jest definiowana przy użyciu wyłącznie maszyn deterministycznych. Jeśli pozwolimy, aby weryfikator był probabilistyczny (niekoniecznie jest to maszyna BPP), otrzymamy klasę MA rozwiązywalną przy użyciu protokołu Arthur-Merlin bez komunikacji między Arturem a Merlinem.

NP to klasa problemów decyzyjnych ; analogiczną klasą problemów funkcjonalnych jest FNP .

Jedyne znane ścisłe inkluzje pochodzą z twierdzenia o hierarchii czasowej i twierdzenia o hierarchii przestrzennej i odpowiednio są to i . ${\displaystyle {\mathsf {NP\subsetneq NEXPTIME}}}$${\displaystyle {\mathsf {NP\subsetneq EXPSPACE}}}$

Inne charakterystyki

Z punktu widzenia opisowej teorii złożoności NP odpowiada dokładnie zbiorowi języków definiowalnych przez egzystencjalną logikę drugiego rzędu ( twierdzenie Fagina ).

NP można traktować jako bardzo prosty rodzaj interaktywnego systemu dowodowego , w którym weryfikator wymyśla certyfikat dowodu, a weryfikator jest deterministyczną maszyną wielomianową, która go sprawdza. Jest kompletna, ponieważ odpowiedni ciąg dowodowy sprawi, że zaakceptuje, jeśli taki istnieje, i jest słuszny, ponieważ weryfikator nie może zaakceptować, jeśli nie ma akceptowalnego ciągu dowodowego.

Głównym wynikiem teorii złożoności jest to, że NP można scharakteryzować jako problemy, które można rozwiązać za pomocą probabilistycznie sprawdzalnych dowodów, w których weryfikator używa losowych bitów O(log n ) i bada tylko stałąliczbębitów ciągu dowodowego (klasa PCP (log n , 1)). Mówiąc bardziej nieformalnie, oznacza to, że opisany powyżej weryfikator NP można zastąpić takim, który po prostu „wyrywkowo sprawdza” kilka miejsc w ciągu dowodowym, a przy użyciu ograniczonej liczby rzutów monetą może z dużym prawdopodobieństwem określić poprawną odpowiedź. Pozwala to na udowodnienie kilku wyników dotyczących twardości algorytmów aproksymacji .

Przykład

Oto lista niektórych problemów, które występują w NP:

Wszystkie problemy w P , oznaczone . Mając certyfikat dla problemu w P , możemy zignorować certyfikat i po prostu rozwiązać problem w czasie wielomianowym. ${\displaystyle {\mathsf {P\subseteq NP}}}$

Wersja decyzyjna problemu komiwojażera znajduje się w NP. Biorąc pod uwagę macierz wejściową odległości między n miastami, problemem jest ustalenie, czy istnieje trasa obejmująca wszystkie miasta o łącznej odległości mniejszej niż k .

Dowodem może być po prostu lista miast. Wtedy weryfikację można wyraźnie przeprowadzić w czasie wielomianowym. Po prostu dodaje wpisy macierzy odpowiadające ścieżkom między miastami.

Niedeterministyczny maszyna Turinga może znaleźć taką drogę, co następuje:

• W każdym odwiedzanym mieście „odgadnie” następne miasto, które odwiedzi, dopóki nie odwiedzi każdego wierzchołka. Jeśli utknie, natychmiast się zatrzyma.
• Na koniec sprawdza, czy przebyta trasa kosztowała mniej niż k w czasie O ( n ).

Można myśleć o każdym przypuszczeniu jako „ rozgałęzianiu ” nowej kopii maszyny Turinga, aby podążać każdą z możliwych ścieżek naprzód, a jeśli przynajmniej jedna maszyna znajdzie trasę o odległości mniejszej niż k , ta maszyna zaakceptuje dane wejściowe. (Równoważnie można to traktować jako pojedynczą maszynę Turinga, która zawsze odgaduje poprawnie)

Binarne wyszukiwania na zakres możliwych dystansach może przekonwertować wersję decyzji o komiwojażera do wersji optymalizacji, wywołując wersję decyzji wielokrotnie (numer wielomian razy).

Wersja problemem decyzja problemu faktoryzacji całkowita : Podane liczby całkowite n i k , istnieje czynnik f z 1 < f < K i F podzielenie n ?

Izomorfizm problemem podgrafu określania czy wykres G zawiera subgraph który jest izomorficzny wykres H .

Problem spełnialności , gdzie chcemy wiedzieć, czy pewną formułę rachunku zdań ze zmiennymi logicznych jest prawdziwe dla pewnej wartości zmiennych.

Zobacz też

• Maszyna Turinga

Uwagi

Bibliografia

Dalsza lektura

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN  0-262-03293-7 . Sekcja 34.2: Weryfikacja wielomianowa, s. 979–983.
• Michaela Sipsera (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. Numer ISBN 0-534-94728-X. Sekcje 7.3–7.5 (Klasa NP, NP-zupełność, Dodatkowe problemy NP-zupełne), s. 241–271.
• David Harel , Yishai Feldman . Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.

Zewnętrzne linki

• Złożoność Zoo : NP
• Elementarz amerykańskiego naukowca na temat tradycyjnych i najnowszych badań nad teorią złożoności: „Algorytmy przypadkowe”