DAA - klasa P i NP
W informatyce wiele problemów rozwiązuje się, gdy celem jest maksymalizacja lub minimalizacja pewnych wartości, podczas gdy w innych problemach staramy się znaleźć rozwiązanie, czy nie. Dlatego problemy można podzielić na następujące kategorie:
Problem optymalizacji
Problemy optymalizacji to te, których celem jest maksymalizacja lub minimalizacja niektórych wartości. Na przykład,
Znalezienie minimalnej liczby kolorów potrzebnych do pokolorowania danego wykresu.
Znajdowanie najkrótszej ścieżki między dwoma wierzchołkami na wykresie.
Problem decyzyjny
Istnieje wiele problemów, na które odpowiedź brzmi „tak” lub „nie”. Te typy problemów są znane jako decision problems. Na przykład,
Czy dany wykres można pokolorować tylko czterema kolorami.
Znalezienie na wykresie cyklu Hamiltona nie jest problemem decyzyjnym, podczas gdy sprawdzenie, czy wykres jest hamiltonowem, czy nie, jest problemem decyzyjnym.
Co to jest język?
Każdy problem decyzyjny może mieć tylko dwie odpowiedzi, tak lub nie. W związku z tym problem decyzyjny może należeć do języka, jeśli zapewnia odpowiedź „tak” dla określonego wkładu. Język to ogół danych wejściowych, dla których odpowiedź brzmi „tak”. Większość algorytmów omówionych w poprzednich rozdziałach topolynomial time algorithms.
Dla rozmiaru wejściowego n, jeśli w najgorszym przypadku złożoność czasowa algorytmu wynosi O(nk), gdzie k jest stałą, algorytm jest algorytmem czasu wielomianowego.
Algorytmy, takie jak mnożenie łańcucha macierzy, najkrótsza ścieżka pojedynczego źródła, najkrótsza ścieżka wszystkich par, minimalne drzewo rozpinające itp., Działają w czasie wielomianowym. Istnieje jednak wiele problemów, takich jak podróżujący sprzedawca, optymalne kolorowanie wykresów, cykle Hamiltona, znalezienie najdłuższej ścieżki na wykresie i spełnienie wzoru Boole'a, dla którego nie są znane żadne algorytmy wielomianowe. Te problemy należą do interesującej klasy problemów, zwanejNP-Complete problemy, których stan jest nieznany.
W tym kontekście możemy podzielić problemy w następujący sposób -
Klasa P.
Klasa P składa się z tych problemów, które można rozwiązać w czasie wielomianowym, tj. Problemy te można rozwiązać w czasie O(nk) w najgorszym przypadku, gdzie k jest stała.
Te problemy są nazywane tractable, podczas gdy inni są wzywani intractable or superpolynomial.
Formalnie algorytm jest algorytmem czasu wielomianowego, jeśli istnieje wielomian p(n) tak, że algorytm może rozwiązać każdy rozmiar n za jakiś czas O(p(n)).
Problem wymagający Ω(n50) czas na rozwiązanie jest zasadniczo trudny do rozwiązania dla dużych n. Najbardziej znany algorytm czasu wielomianowego działa w czasieO(nk) za dość niską wartość k.
Zaletą rozważania klasy algorytmów wielomianowych jest to, że wszystko jest rozsądne deterministic single processor model of computation można symulować na sobie co najwyżej wielomianem slow-d
Klasa NP
Klasa NP składa się z tych problemów, które są weryfikowalne w czasie wielomianowym. NP to klasa problemów decyzyjnych, w przypadku których można łatwo sprawdzić poprawność żądanej odpowiedzi, korzystając z dodatkowych informacji. Dlatego nie prosimy o znalezienie rozwiązania, a jedynie o zweryfikowanie, czy rzekome rozwiązanie jest naprawdę poprawne.
Każdy problem w tej klasie można rozwiązać w czasie wykładniczym za pomocą wyszukiwania wyczerpującego.
P kontra NP
Każdy problem decyzyjny, który można rozwiązać za pomocą deterministycznego algorytmu wielomianowego czasu, jest również rozwiązany przez niedeterministyczny algorytm wielomianowy.
Wszystkie problemy w P można rozwiązać za pomocą algorytmów wielomianowych, podczas gdy wszystkie problemy w NP - P są nie do rozwiązania.
Nie wiadomo, czy P = NP. Jednak w NP znanych jest wiele problemów z własnością, że jeśli należą do P, to można udowodnić, że P = NP.
Jeśli P ≠ NP, są problemy w NP, których nie ma ani w P, ani w NP-Complete.
Problem należy do klasy Pczy łatwo jest znaleźć rozwiązanie problemu. Problem należy doNP, jeśli łatwo jest sprawdzić rozwiązanie, które mogło być bardzo uciążliwe.