Loading AI tools
problem decyzyjny Z Wikipedii, wolnej encyklopedii
Problem NP (ang. nondeterministic polynomial, niedeterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.
Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność.
Przykładowy problem:
Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym. Nasuwający się algorytm sprawdzenia wszystkich możliwych podzbiorów ma złożoność wykładniczą ze względu na liczebność zbioru. Nie wiadomo zatem, czy problem ten jest klasy P. Na pewno natomiast uzyskawszy z zewnątrz kandydata na rozwiązanie (np. ) możemy w liniowym (a zatem wielomianowym) czasie sprawdzić, czy sumuje się do zera. Jest to zatem problem NP.
W szczególności wszystkie problemy klasy P są NP, ponieważ można je sprawdzić w czasie wielomianowym. Innymi słowy, klasa P zawiera się nieostro w NP Nie wiadomo natomiast, czy istnieje problem NP, który nie jest w klasie P (czyli, czy P różni się od NP lub inaczej albo )[2]. Jest to jeden z problemów milenijnych.
Podejmowano kilka prób oszacowania, kiedy ten problem może być rozstrzygnięty:
Klasa złożoności NP może być zdefiniowana w kategorii klas NTIME(f(n)) w następujący sposób:
Alternatywnie, klasę NP można zdefiniować w kontekście deterministycznych maszyn Turinga. Powiemy, że język L należy do NP wtedy i tylko wtedy, gdy istnieją wielomiany p i q, oraz deterministyczna maszyna Turinga M, taka że:
Wiele naturalnych problemów algorytmicznych znajduje się w klasie złożoności NP. W szczególności, decyzyjne wersje wielu interesujących problemów przeszukiwania oraz problemów optymalizacyjnych należą do NP.
W celu wyjaśnienia definicji klasy NP bazującej na weryfikatorach przeanalizujemy problem sumy podzbioru:
Moglibyśmy zaproponować algorytm rozwiązujący powyższy problem, a bazujący na sprawdzaniu wszystkich możliwych podzbiorów. Niestety, liczba podzbiorów, a tym samym czas obliczeń, rośnie wykładniczo w stosunku do rozmiaru podanego zbioru. Zauważmy jednak, że mając podany pewien podzbiór, możemy łatwo sprawdzić, czy suma jego elementów wynosi zero. Jeśli tak jest, mówimy, że dany zbiór jest świadkiem faktu, że odpowiedź na zadany problem jest pozytywna. Algorytm sprawdzający, czy elementy zadanego zbioru sumują się do zera, nazywamy natomiast weryfikatorem.
Bardziej ogólnie, mówimy, że problem obliczeniowy należy do NP, jeśli istnieje dla niego weryfikator V. Mając dowolny egzemplarz I problemu P, dla którego odpowiedź jest pozytywna, musi istnieć świadek S, taki że V akceptuje słowo wejściowe (I, S) w czasie wielomianowym. Co więcej, jeśli odpowiedź na I jest negatywna, weryfikator V odrzuci słowo (I, S) dla wszystkich możliwych S. Zauważ, że weryfikator może odrzucić wejście nawet, gdy odpowiedź jest pozytywna, jeśli tylko S nie jest poprawnym świadkiem. Dla przykładu, w przypadku problemu sumy podzbioru, jeśli istnieje podzbiór, którego elementy sumują się do zera, ale jako świadek S wybrany zostanie inny podzbiór, dla którego nie jest to prawdą, weryfikator odrzuci słowo wejściowe. Jeśli jednak nie istnieje podzbiór o zerowej sumie, weryfikator będzie odrzucał wejście niezależnie od wyboru świadka. Ponadto w przypadku tego problemu, weryfikator działa w czasie wielomianowym (potrzeba jedynie sprawdzić, czy S faktycznie jest podzbiorem I oraz czy suma jego elementów jest zerowa), a zatem problem sumy podzbioru należy do klasy NP.
Dopełnienie przytoczonego problemu obliczeniowego może zostać sformułowane w następujący sposób:
Definicja bazująca na weryfikatorach nie wymaga istnienia żadnego łatwego do zweryfikowania świadka dla odpowiedzi negatywnej. Klasę problemów obliczeniowych z takimi świadkami nazywamy co-NP. Problemem otwartym jest czy dla dowolnego problemu obliczeniowego w klasie NP istnieją świadkowie odpowiedzi negatywnych, a zatem czy zawierają się one w co-NP.
Następująca definicja jest równoważna definicji bazującej na weryfikatorach:
Równoważność powyższej definicji z tą bazującą na weryfikatorach opiera się na fakcie, że niedeterministyczna maszyna Turinga można rozwiązać problem z klasy NP w czasie wielomianowym poprzez niedeterministyczny wybór świadka oraz symulację na nim weryfikatora. Z drugiej strony, jeśli istnieje niedeterministyczna maszyna M rozwiązująca pewien problem z NP, możemy łatwo skonstruować weryfikator dla tego problemu. Będzie on w deterministyczny sposób symulował pewien przebieg maszyny M, korzystając ze świadka za każdym razem, gdy należy dokonać niedeterministycznego wyboru.
Poniżej znajduje się niekompletna lista problemów znajdujących się w klasie NP.
Klasa NP jest zamknięta na:
Nie jest wiadome, czy NP jest zamknięte na dopełnienie (jest to tak zwany problem NP vs. co-NP).
Ponieważ w klasie tej znajduje się wiele istotnych problemów, podjęte zostały intensywne prace nad znalezieniem algorytmów działających w czasie wielomianowym rozwiązujących problemy NP. Niemniej jednak, w klasie NP wciąż pozostało wiele problemów, dla których nie udało się opracować takich algorytmów i wydają się one wymagać superwielomianowego czasu obliczeń. Zagadnienie, czy wszystkie takie problemy da się rozwiązać w czasie wielomianowym jest jednym z najważniejszych pytań informatyki (jest to tak zwany problem P vs NP).
Ważnym dla tego problemu pojęciem jest klasa problemów NP-zupełnych, która jest podzbiorem NP i może być nieformalnie rozumiana jako zbiór „najtrudniejszych” problemów NP. Jeśli istnieje wielomianowy algorytm rozwiązujący pewien problem NP-zupełny, to dowolny problem NP można rozwiązać w czasie wielomianowym. W związku z tym, oraz z powodu wielu przeprowadzonych badań skupiających się na znalezieniu wielomianowych rozwiązań dla problemów NP-zupełnych, które zakończyły się niepowodzeniem, jeśli dla danego problemu zostanie udowodnione, że jest on NP-zupełny, to jest wielce prawdopodobne, że nie istnieje dla niego algorytm wielomianowy.
Tym niemniej, dla niektórych problemów NP istnieją algorytmy wielomianowe, które dają rozwiązanie nieoptymalne, ale często wystarczająco dobre. Ponadto rzeczywiste przypadki niektórych problemów są łatwiejsze do rozwiązania niż ich teoretyczne odpowiedniki.
Obie definicje klasy złożoności obliczeniowej NP – ta przedstawiająca ją jako zbiór języków akceptowanych przez niedeterministyczne maszyny Turinga w czasie wielomianowej, oraz ta mówiąca, że są to problemy o rozwiązaniach weryfikowalnych przez deterministyczną maszynę Turinga – są sobie równoważne.
W celu udowodnienia tego faktu przyjmijmy najpierw, że mamy deterministyczny weryfikator. Niedeterministyczna maszyna Turinga może w prosty sposób zasymulować działanie tego weryfikatora na słowie wejściowym oraz wszystkich możliwych świadkach. Wymaga to tylko wielomianowo wiele kroków, ponieważ wybór kolejnego znaku świadka odbywa się w sposób niedeterministyczny, a długość świadka musi być ograniczona z góry przez wielomian względem długości słowa wejściowego. Jeśli dla danego słowa wejściowego istnieje jakikolwiek poprawny świadek, będzie również istniał akceptujący przebieg niedeterministycznej maszyny. Natomiast jeśli świadek nie istnieje, to znaczy, że wszystkie przebiegi maszyny odrzucą słowo wejściowe. Z poprawności weryfikatora wiemy jednak, że słowo takie nie należy do rozważanego języka.
Z drugiej strony, przypuśćmy, że mamy daną niedeterministyczną maszynę Turinga M akceptującą język L w czasie wielomianowym. W każdym z wielomianowo wielu kroków drzewo obliczeń maszyny M może rozgałęziać się na co najwyżej skończoną liczbę różnych przebiegów. Dla danego słowa wejściowego możemy zatem zakodować przebiegi maszyny przy użyciu słów o długości ograniczonej wielomianem względem długości wejścia. Weryfikator może zatem dla podanej na wejściu pary (w, s) symulować przebieg s maszyny M na słowie wejściowym w. Jeśli każdy przebieg maszyny odrzucał w, nie będzie istniał poprawny świadek. Jeśli natomiast maszyna akceptowała to słowo w pewnym przebiegu, to jego kodowanie będzie poprawnym świadkiem.
Dopełnieniem klasy NP nazywamy klasę co-NP, zawierającą takie problemy, gdzie dla każdego słowa wejściowego o odpowiedzi negatywnej istnieje tego świadek (zwany często kontrprzykładem). Przykładowo, problem testu pierwszości jest co-NP, gdyż dobrym świadkiem odpowiedzi negatywnej może być nietrywialny dzielnik zadanej na wejściu liczby.
NP jest klasą problemów decyzyjnych. Analogiczną klasą dla problemów funkcyjnych jest klasa złożoności FNP.
W kategoriach teorii złożoności opisowej (ang. descriptive complexity theory), klasa NP odpowiada zbiorowi języków definiowalnych przez egzystencjalną logikę drugiego rzędu – w skrócie ESO (twierdzenie Fagina).
Klasa NP może być rozumiana jako rodzaj bardzo prostego interaktywnego systemu dowodzenia, w którym dowodzący dostarcza świadka dowodu, a weryfikator jest deterministyczną maszyną Turinga działającą w czasie wielomianowym, która sprawdza poprawność świadka. Takie rozumowanie jest poprawne, ponieważ właściwe słowo-świadek, jeśli takie istnieje, zostanie zaakceptowane przez weryfikator oraz weryfikator nie zaakceptuje wejścia, jeśli poprawny świadek nie istnieje.
Ważnym rezultatem teorii złożoności obliczeniowej jest fakt, że NP może być określone jako klasa tych problemów, które są rozwiązywalne przez system PCP (ang. probabilistically checkable proof, dowód weryfikowalny probablistycznie), w którym weryfikator używa O(log n) losowych bitów oraz korzysta tylko ze stałej liczby bitów słowa-świadka (klasa PCP(log n, 1)). Prostszymi słowami, oznacza to, że weryfikator dla problemów NP omawiany we wcześniejszych sekcjach może być zastąpiony przez taki, który wykonuje tylko ustaloną liczbę odczytów pewnych fragmentów świadka, a następnie logarytmicznie wiele razy rzuca monetą i na podstawie tego jest w stanie określić poprawność świadka z dużym prawdopodobieństwem. Rezultat ten pozwolił udowodnić kilka faktów odnośnie do algorytmów aproksymacyjnych.
Wersja decyzyjna problemu komiwojażera należy do klasy NP i jest sformułowana następująco:
Świadkiem może być oczywiście lista kolejnych miast na wynikowej trasie. Weryfikacja może przeprowadzona w czasie wielomianowym przez deterministyczną maszynę Turinga poprzez proste zsumowanie wartości w komórkach macierzy opowiadających odległościom między kolejnymi miastami.
Niedeterministyczna maszyna Turinga może znaleźć odpowiednią trasę w następujący sposób:
O niedeterministycznym wyborze można myśleć jak o sklonowaniu maszyny Turinga wraz z jej stanem, tak aby każda z maszyn sprawdziła inny możliwy przebieg. Jeśli co najmniej jedna z maszyn odnajdzie trasę krótszą niż k, maszyna niedeterministyczna akceptuje wejście. Można również wyobrażać to sobie jako pojedynczą maszynę Turinga, która zawsze odgaduje poprawnie, które miasto należy odwiedzić jako następne tak, aby trasa nie przekracza zadanego limitu.
Poprzez wyszukiwanie binarne po przedziale możliwych sumarycznych długości tras (ograniczone przez iloczyn liczby miast n oraz maksymalną wartość w macierzy odległości) można sprowadzić optymalizacyjną wersję problemu komiwojażera do wersji decyzyjnej.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
