Co to jest „P = NP?” I dlaczego jest tak znanym pytaniem? [Zamknięte]

Pytanie, czy P = NP jest być może najbardziej znanym w całej informatyce. Co to znaczy? A dlaczego to takie interesujące?

Aha, i dla dodatkowego uznania, proszę opublikować dowód prawdziwości lub fałszu oświadczenia. :)

P oznacza czas wielomianowy. NP oznacza niedeterministyczny czas wielomianowy.

Definicje:

• Czas wielomianowy oznacza, że ​​złożoność algorytmu wynosi O (n ^ k), gdzie n jest rozmiarem twoich danych (np. Liczba elementów na liście do posortowania), a k jest stałą.

• Złożoność to czas mierzony liczbą operacji, które musiałby podjąć, w zależności od liczby elementów danych.

• Operacja jest czymkolwiek, co ma sens jako podstawowa operacja dla określonego zadania. Podstawową operacją sortowania jest porównanie. W przypadku mnożenia macierzy podstawową operacją jest mnożenie dwóch liczb.

Pytanie brzmi: co oznacza deterministyczny vs. niedeterministyczny? Istnieje abstrakcyjny model obliczeniowy, wyimaginowany komputer o nazwie maszyna Turinga (TM). Ta maszyna ma skończoną liczbę stanów i nieskończoną taśmę, która ma dyskretne komórki, w których można zapisać i odczytać skończony zestaw symboli. W dowolnym momencie TM znajduje się w jednym ze swoich stanów i patrzy na określoną komórkę na taśmie. W zależności od tego, co czyta z tej komórki, może zapisać nowy symbol w tej komórce, przesunąć taśmę o jedną komórkę do przodu lub do tyłu i przejść do innego stanu. Nazywa się to przejściem stanu. O dziwo, poprzez staranne konstruowanie stanów i przejść, możesz zaprojektować bazę TM, która jest odpowiednikiem każdego programu komputerowego, który można napisać.

Istnieją dwa rodzaje TM, które nas tutaj dotyczą: deterministyczne i niedeterministyczne. Deterministyczna TM ma tylko jedno przejście z każdego stanu dla każdego symbolu, który odczytuje z taśmy. Niedeterministyczna TM może mieć kilka takich przejść, tj. Jest w stanie sprawdzić kilka możliwości jednocześnie. To trochę jak spawnowanie wielu wątków. Różnica polega na tym, że niedeterministyczna TM może spawnować tyle „wątków”, ile chce, podczas gdy na prawdziwym komputerze można wykonać tylko określoną liczbę wątków naraz (równą liczbie procesorów). W rzeczywistości komputery to zasadniczo deterministyczne TM z skończonymi taśmami. Z drugiej strony, niedeterministyczna TM nie może być fizycznie zrealizowana, chyba że z komputerem kwantowym.

Udowodniono, że każdy problem, który można rozwiązać za pomocą niedeterministycznej TM, można rozwiązać za pomocą deterministycznej TM. Nie jest jednak jasne, ile czasu to zajmie. Stwierdzenie P = NP oznacza, że ​​jeśli problem zajmuje czas wielomianowy na niedeterministycznej TM, to można zbudować deterministyczną TM, która rozwiązałaby ten sam problem również w czasie wielomianowym. Do tej pory nikt nie był w stanie wykazać, że da się to zrobić, ale nikt nie był w stanie udowodnić, że nie można tego zrobić.

Problem NP-zupełny oznacza problem NP X, tak że każdy problem NP NP może zostać zredukowany do X przez redukcję wielomianową. Oznacza to, że jeśli ktokolwiek kiedykolwiek wymyśli rozwiązanie problemu wielomianowego NP-zupełnego, da to również rozwiązanie problemu wielomianowego dowolnego problemu NP. Dowodzi to zatem, że P = NP. I odwrotnie, jeśli ktokolwiek miałby udowodnić, że P! = NP, bylibyśmy pewni, że nie ma sposobu na rozwiązanie problemu NP w czasie wielomianowym na konwencjonalnym komputerze.

Przykładem problemu NP-zupełnego jest problem ze znalezieniem przypisania prawdy, dzięki któremu wyrażenie boolowskie zawierające n zmiennych będzie prawdziwe.
Na chwilę obecną każdy problem, który zajmuje czas wielomianowy na niedeterministycznej TM, może zostać rozwiązany tylko w czasie wykładniczym na deterministycznej TM lub na konwencjonalnym komputerze.
Na przykład jedynym sposobem rozwiązania problemu przypisania prawdy jest wypróbowanie 2 ^ n możliwości.

1. Problem typu „tak lub nie” występuje w P ( P olynomial czasu) Jeśli odpowiedź może być obliczane w czasie wielomianowym.
2. Tak-lub-nie ma problemu w NP ( N na deterministycznej P olynomial czasu) jeżeli odpowiedź tak można zweryfikować w czasie wielomianowym.

Intuicyjnie widzimy, że jeśli problem występuje w P , to w NP . Biorąc pod uwagę potencjalną odpowiedź na problem w P. , możemy zweryfikować odpowiedź, po prostu przeliczając odpowiedź.

Mniej oczywiste, a znacznie trudniej odpowiedzieć, czy wszystkie problemy NP są w P . Czy fakt, że możemy zweryfikować odpowiedź w czasie wielomianowym oznacza, że ​​możemy obliczyć tę odpowiedź w czasie wielomianowym?

Istnieje wiele ważnych problemów, o których wiadomo, że są kompletne z NP (w zasadzie, jeśli jakikolwiek z tych problemów zostanie wykazany w P , wówczas wszystkie problemy z NP są w P ). Jeśli P = NP , wówczas wszystkie te problemy będą miały skuteczne rozwiązanie (czas wielomianowy).

Większość naukowców uważa, że P ! = NP . Jednak żaden dowód nie został jeszcze ustalony dla P = NP lub P ! = NP . Jeśli ktokolwiek dostarczy dowód na którąkolwiek hipotezę, wygra 1 milion USD .

Aby dać najprostszą odpowiedź, o której mogę pomyśleć:

Załóżmy, że mamy problem, który wymaga pewnej liczby danych wejściowych i ma różne potencjalne rozwiązania, które mogą, ale nie muszą rozwiązać problemu dla danych danych wejściowych. Logiczna łamigłówka w magazynie z łamigłówkami byłaby dobrym przykładem: dane wejściowe to warunki („George nie mieszka w niebieskim lub zielonym domu”), a potencjalnym rozwiązaniem jest lista stwierdzeń („George mieszka na żółto dom, hoduje groszek i jest właścicielem psa "). Znanym przykładem jest problem Traveling Salesman: biorąc pod uwagę listę miast, czasy dojazdu z jednego miasta do innego oraz limit czasowy, potencjalnym rozwiązaniem może być lista miast w kolejności, w jakiej odwiedza je sprzedawca, oraz zadziałałoby, gdyby suma czasów podróży była mniejsza niż termin.

Taki problem występuje w NP, jeśli możemy skutecznie sprawdzić potencjalne rozwiązanie, aby sprawdzić, czy to działa. Na przykład, biorąc pod uwagę listę miast, które sprzedawca może odwiedzić w celu zamówienia, możemy zsumować czas każdej podróży między miastami i łatwo sprawdzić, czy jest ona przekroczona. Problem występuje w P, jeśli możemy skutecznie znaleźć rozwiązanie, jeśli takie istnieje.

(Tutaj efektywnie ma dokładne matematyczne znaczenie. W praktyce oznacza to, że duże problemy nie są nierozsądnie trudne do rozwiązania. Poszukując możliwego rozwiązania, nieefektywnym sposobem byłoby wyliczenie wszystkich możliwych potencjalnych rozwiązań lub czegoś zbliżonego do tego , podczas gdy skuteczny sposób wymagałby wyszukiwania znacznie bardziej ograniczonego zestawu).

Dlatego problem P = NP można wyrazić w ten sposób: Jeśli potrafisz skutecznie zweryfikować rozwiązanie problemu opisanego powyżej, czy możesz skutecznie znaleźć rozwiązanie (lub udowodnić, że go nie ma)? Oczywista odpowiedź brzmi: „Dlaczego powinieneś być w stanie?”, I to właśnie w tym miejscu stoi dzisiaj sprawa. Nikt nie był w stanie tego udowodnić w ten czy inny sposób, co niepokoi wielu matematyków i informatyków. Dlatego każdy, kto może udowodnić rozwiązanie, zarabia milion dolarów od Claypool Foundation.

Ogólnie zakładamy, że P nie jest równe NP, że nie ma ogólnego sposobu na znalezienie rozwiązań. Gdyby okazało się, że P = NP, wiele rzeczy by się zmieniło. Na przykład kryptografia stałaby się niemożliwa, a wraz z nią jakakolwiek prywatność lub weryfikowalność w Internecie. W końcu możemy efektywnie pobrać zaszyfrowany tekst i klucz i wygenerować oryginalny tekst, więc jeśli P = NP, możemy skutecznie znaleźć klucz, nie znając go wcześniej. Łamanie haseł stałoby się banalne. Z drugiej strony istnieje cała klasa problemów związanych z planowaniem i problemami z alokacją zasobów, które moglibyśmy skutecznie rozwiązać.

Być może słyszałeś opis NP-complete. Problem NP-zupełny to taki, który jest NP (oczywiście) i ma tę interesującą właściwość: jeśli jest w P, każdy problem NP jest, a więc P = NP. Jeśli potrafisz znaleźć sposób na skuteczne rozwiązanie problemu Traveling Salesman lub logiczne łamigłówki z puzzli, możesz skutecznie rozwiązać wszystko w NP. Problem NP-zupełny jest w pewnym sensie najtrudniejszym rodzajem problemu NP.

Tak więc, jeśli potrafisz znaleźć skuteczną ogólną technikę rozwiązania dowolnego problemu z NP-zakończeniem lub udowodnić, że nie istnieje, sława i fortuna są twoje.

Krótkie streszczenie mojej skromnej wiedzy:

Istnieją pewne proste problemy obliczeniowe (takie jak znalezienie najkrótszej ścieżki między dwoma punktami na wykresie), które można obliczyć dość szybko (O (n ^ k), gdzie n jest rozmiarem danych wejściowych, a k jest stałą (w w przypadku wykresów jest to liczba wierzchołków lub krawędzi)).

Inne problemy, takie jak znalezienie ścieżki, która przecina każdy wierzchołek na wykresie lub uzyskanie klucza prywatnego RSA z klucza publicznego, jest trudniejsze (O (e ^ n)).

Ale CS Speak mówi, że problem polega na tym, że nie możemy „przekształcić” niedeterministycznej maszyny Turinga w deterministyczną, możemy jednak przekształcić niedeterministyczne skończone automaty (takie jak parser wyrażeń regularnych) w deterministyczne (no cóż, ty może, ale czas działania maszyny potrwa długo). Oznacza to, że musimy wypróbować każdą możliwą ścieżkę (zwykle inteligentni profesorowie CS mogą wykluczyć kilka).

Jest to interesujące, ponieważ nikt nawet nie ma pojęcia o rozwiązaniu. Niektórzy twierdzą, że to prawda, inni twierdzą, że to nieprawda, ale nie ma konsensusu. Inną interesującą rzeczą jest to, że rozwiązanie byłoby szkodliwe dla szyfrowania klucza publicznego / prywatnego (takiego jak RSA). Możesz je złamać tak łatwo, jak teraz generowanie klucza RSA.

I to jest dość inspirujący problem.

Niewiele mogę dodać do tego, co i dlaczego części pytania P =? NP, ale w odniesieniu do dowodu. Dowód byłby nie tylko wart dodatkowego kredytu, ale rozwiązałby jeden z problemów milenijnych . Niedawno przeprowadzono interesującą ankietę, a opublikowane wyniki (PDF) są zdecydowanie warte przeczytania w odniesieniu do tematu dowodu.

Po pierwsze, niektóre definicje:

• Szczególnym problemem jest P, jeśli można obliczyć rozwiązanie w czasie krótszym niż n^kdla niektórych k, gdzie njest wielkość danych wejściowych. Na przykład, sortowanie może być wykonane, w n log nktórym jest mniej niż n^2, więc sortowanie jest czasem wielomianowym.

• Problem występuje w NP, jeśli istnieje ktakie rozwiązanie, że istnieje rozwiązanie o rozmiarze co najwyżej, n^kktóre można zweryfikować w czasie n^k. Weź 3-kolorowanie wykresów: biorąc pod uwagę wykres, 3-kolorowanie to lista par (wierzchołek, kolor), która ma rozmiar O(n)i możesz z czasem O(m)(lub O(n^2)) sprawdzić, czy wszyscy sąsiedzi mają różne kolory. Tak więc wykres jest trójkolorowy tylko wtedy, gdy istnieje krótkie i łatwe do zweryfikowania rozwiązanie.

Równoważną definicją NP są „problemy rozwiązywane przez N- deterministyczną maszynę Turinga w P. olynomial time”. Chociaż mówi ci, skąd pochodzi nazwa, nie daje tego samego intuicyjnego odczucia, jakie są problemy NP.

Zauważ, że P jest podzbiorem NP: jeśli możesz znaleźć rozwiązanie w czasie wielomianowym, istnieje rozwiązanie, które można zweryfikować w czasie wielomianowym - po prostu sprawdź, czy dane rozwiązanie jest równe temu, które możesz znaleźć.

Dlaczego pytanie jest P =? NPinteresujące? Aby odpowiedzieć na to pytanie, najpierw trzeba zobaczyć, jakie są problemy z kompletnością NP. Mówiąc prościej,

• Problem L jest NP-kompletny, jeśli (1) L jest w P, i (2) algorytm, który rozwiązuje L, może być użyty do rozwiązania dowolnego problemu L 'w NP; to znaczy, biorąc pod uwagę instancję L ', możesz utworzyć instancję L, która ma rozwiązanie wtedy i tylko wtedy, gdy instancja L' ma rozwiązanie. Formalnie rzecz biorąc, każdy problem L 'w NP można sprowadzić do L.

Zauważ, że instancja L musi być obliczalna w czasie wielomianowym i mieć rozmiar wielomianowy, w rozmiarze L '; w ten sposób rozwiązanie problemu NP-zupełnego w czasie wielomianowym daje wszystkim rozwiązanie czasu wielomianowego problemów NP.

Oto przykład: załóżmy, że wiemy, że 3-kolorowanie wykresów jest trudnym problemem NP. Chcemy udowodnić, że decydowanie o tym, czy formuły boolowskie są zadowalające, jest również trudnym zadaniem NP.

Dla każdego wierzchołka v mają dwie zmienne logiczne v_h i v_l oraz wymaganie (v_h lub v_l): każda para może mieć tylko wartości {01, 10, 11}, które możemy traktować jako kolor 1, 2 i 3.

Dla każdej krawędzi (u, v), wymagaj, aby (u_h, u_l)! = (V_h, v_l). To jest,

not ((u_h and not u_l) and (v_h and not v_l) or ...) wyliczając wszystkie równe konfiguracje i zastrzegając, że żadna z nich nie ma miejsca.

ANDpołączenie tych wszystkich ograniczeń daje formułę logiczną, która ma wielkość wielomianową ( O(n+m)). Możesz sprawdzić, czy obliczenie zajmuje również czas wielomianowy: robisz to prostoO(1) rzeczy na wierzchołek i na krawędź.

Jeśli potrafisz rozwiązać formułę boolowską, którą stworzyłem, możesz także rozwiązać kolorowanie wykresów: dla każdej pary zmiennych v_h i v_l, niech kolor v będzie tym, który odpowiada wartościom tych zmiennych. Dzięki konstrukcji formuły sąsiedzi nie będą mieć jednakowych kolorów.

Stąd, jeśli 3-barwienie grafów jest NP-kompletne, to również jest spełnienie formuły logicznej.

Wiemy, że 3-kolorowanie wykresów jest NP-kompletne; jednakże historycznie dowiedzieliśmy się, że najpierw wykazując kompletność NP dla satysfakcjonującego obwodu logicznego, a następnie redukując ją do 3-kolorowalności (zamiast na odwrót).