Co to jest " P = NP?", i dlaczego jest to takie słynne pytanie? [zamknięte]

1. A tak-or-no problem is in P (P czas olynomialny), jeśli odpowiedź można obliczyć w czasie wielomianowym.
2. A tak-or-no problem is in NP (Non-deterministyczny Pczas olynomialny), jeśli odpowiedź Tak może być zweryfikowana w czasie wielomianowym.

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

Mniej oczywiste, a znacznie trudniejsze do odpowiedzi, jest to, czy wszystkie problemy w NP są wP . Czy fakt, że możemy zweryfikować odpowiedź w czasie wielomianowym oznacza, że możemy obliczyć tę odpowiedź w czasie wielomianowym?

Istnieje duża liczba ważnych problemów, które są znane jako NP -kompletne (zasadniczo, jeśli jakiekolwiek te problemy są udowodnione w P, to wszystkie np problemy okazały się w P ). If P = NP , wtedy wszystkie te problemy zostaną udowodnione jako efektywne (czas wielomianowy) rozwiązanie.

Większość naukowców uważa, że P != NP . Jednakże nie ustalono jeszcze żadnego dowodu na P = NP lub P != NP . Jeśli ktoś dostarczy dowód na którąkolwiek z hipotez, wygra 1 milion dolarów.

Aby dać najprostszą odpowiedź jaką przychodzi mi do głowy:

Załóżmy, że mamy problem, który pobiera określoną liczbę wejść i ma różne potencjalne rozwiązania, które mogą lub nie mogą rozwiązać problemu dla danych wejść. Dobrym przykładem może być logiczna łamigłówka w magazynie puzzle: wejściami są warunki ("George nie mieszka w niebieskim lub zielonym domu"), a potencjalnym rozwiązaniem jest lista stwierdzeń ("George mieszka w żółtym domu, rośnie groszek i jest właścicielem psa"). Sławny przykładem jest problem podróżujących sprzedawców: biorąc pod uwagę listę miast i czasy, aby dostać się z dowolnego miasta do dowolnego innego, a limit czasu, potencjalne rozwiązanie byłoby lista miast w kolejności sprzedawca odwiedza je, i to działa, jeśli suma czasu podróży była mniejsza niż limit czasu.

Taki problem jest w NP, jeśli możemy sprawnie sprawdzić potencjalne rozwiązanie, aby sprawdzić, czy działa. Na przykład, biorąc pod uwagę listę miast do odwiedzenia przez Sprzedawcę w kolejności, możemy dodać czasy dla każdej podróży między miastami i łatwo sprawdzić, czy nie jest w terminie. Problem jest w P, jeśli możemy skutecznie znaleźć rozwiązanie, jeśli takie istnieje.

(efektywnie, tutaj, ma precyzyjne znaczenie matematyczne. Praktycznie oznacza to, że duże problemy nie są nierozsądnie trudne do rozwiązania. Szukając możliwego rozwiązania, nieefektywnym sposobem byłoby wykazanie wszystkich możliwych potencjalnych rozwiązań, lub coś podobnego, podczas gdy skuteczny sposób wymagałby wyszukiwania dużo bardziej ograniczony zestaw.)

Dlatego problem P=NP można wyrazić w ten sposób: jeśli uda się sprawnie zweryfikować rozwiązanie problemu opisanego powyżej, czy uda się znaleźć rozwiązanie (lub udowodnić, że nie istnieje) skutecznie? Oczywistą odpowiedzią jest "dlaczego powinieneś być w stanie?", i to jest praktycznie tam, gdzie sprawa stoi dzisiaj. Nikt nie był w stanie tego udowodnić w taki czy inny sposób, a to przeszkadza wielu matematykom i informatykom. Dlatego każdy, kto może udowodnić rozwiązanie jest na milion dolarów od Fundacji Claypool.

Ogólnie Zakładamy, że P nie równa się NP, że nie ma ogólnego sposobu znalezienia rozwiązań. Gdyby się okazało, że P = NP, wiele by się zmieniło. Na przykład kryptografia byłaby niemożliwa, a wraz z nią wszelka prywatność lub weryfikowalność w Internecie. W końcu możemy efektywnie wziąć zaszyfrowany tekst i klucz i wyprodukować oryginalny tekst, więc jeśli P = NP moglibyśmy efektywnie znaleźć klucz nie wiedząc o tym wcześniej. Łamanie haseł stanie się banalne. Z drugiej strony istnieją całe klasy problemów z planowaniem i 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, to każdy problem NP jest, a więc P=NP. Jeśli uda Ci się znaleźć sposób na skuteczne rozwiązanie problemu podróżnego Sprzedawcy lub zagadek logicznych z magazynów logicznych, można skutecznie rozwiązać wszystko w np. Problem np-kompletny jest w pewnym sensie najtrudniejszym rodzajem problemu NP.

Więc, jeśli możesz znaleźć skuteczną technikę ogólnego rozwiązania dowolnego problemu NP-complete, lub udowodnić, że takiego nie ma, sława i fortuna są Twoje.

Krótkie podsumowanie z mojej skromnej wiedzy:

Istnieją pewne proste problemy obliczeniowe (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 wielkością wejścia, A k jest stałą (w przypadku wykresów jest to liczba wierzchołków lub krawędzi)).

Inne problemy, takie jak znalezienie ścieżki, która przekracza każdy wierzchołek grafu lub uzyskanie klucza prywatnego RSA z klucza publicznego, są 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 automaty skończone (jak parser regex) w deterministyczne (cóż, możesz, ale czas działania maszyny zajmie dużo czasu). Oznacza to, że musimy wypróbować każdą możliwą ścieżkę (Zwykle inteligentni profesorowie CS mogą wykluczyć kilka z nich).

To ciekawe, bo nikt nawet nie ma pomysłu na rozwiązanie. Niektórzy mówią, że to prawda, niektórzy mówią, że to fałsz, ale nie ma konsensusu. Inną ciekawą rzeczą jest to, że rozwiązanie byłoby szkodliwe dla szyfrowania kluczy publicznych/prywatnych (takich jak RSA). Możesz je złamać tak łatwo, jak Generowanie klucza RSA jest teraz.

I to jest dość inspirujący problem.

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

Po pierwsze, niektóre definicje:

• Szczególny problem jest w P, jeśli można obliczyć rozwiązanie w czasie mniejszym niż n^k dla pewnego k, Gdzie n jest wielkością wejścia. Na przykład, sortowanie może być wykonane w n log n, która jest mniejsza niż n^2, więc sortowanie jest czasem wielomianowym.

• Problem jest w NP jeśli istnieje k takie, że istnieje rozwiązanie wielkości co najwyżej n^k które można zweryfikować w czasie co najwyżej n^k. Take 3-kolorowanie Wykresów: podane Wykres, 3-kolorowanie jest listą (wierzchołek, kolor) par, które mają rozmiar O(n) i można sprawdzić w czasie O(m) (lub O(n^2)), czy wszyscy sąsiedzi mają różne kolory. Tak więc wykres jest 3-kolorowalny tylko wtedy, gdy istnieje krótkie i łatwo weryfikowalne rozwiązanie.

Równoważną definicją NP jest "problemy rozwiązywalne przez N ondeterministyczną maszynę Turinga w P olynomial time". Chociaż mówi ci, skąd pochodzi nazwa, to nie daje ci tego samego intuicyjne odczucie, jak wyglądają problemy z 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 P =? NP jest interesujące? Aby na to odpowiedzieć, najpierw trzeba zobaczyć, czym są problemy np-complete. Po prostu,

• problem L jest np-zupełny, Jeśli (1) L jest w P, A (2) algorytm, który rozwiązuje L można użyć do rozwiązania dowolnego problemu L 'w NP; to znaczy, biorąc pod uwagę instancję L' można 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 jest redukowalny do L.

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

Oto przykład: załóżmy, że wiemy, że 3-kolorowanie Wykresów jest problemem NP-hard. Chcemy udowodnić, że decydowanie o spełnialności formuł boolowskich jest również trudnym problemem.

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

Dla każdej krawędzi (u, v), ma wymóg, że (u_h, u_l) != (v_h, v_l). Czyli

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.

AND'razem wszystkie te ograniczenia daje wzór Boole' a, który ma rozmiar wielomianu (O(n+m)). Możesz sprawdzić, czy obliczanie wielomianu zajmuje również czas: robisz proste O(1) rzeczy na wierzchołek i na krawędź.

Jeśli możesz rozwiązać formułę boolowską, którą stworzyłem, to możesz również rozwiązać Graf kolorowanie: dla każdej pary zmiennych v_h i v_l, niech kolor v będzie tym pasującym do wartości tych zmiennych. Dzięki konstrukcji wzoru sąsiedzi nie będą mieli równych kolorów.

Stąd, Jeśli 3-kolorowanie grafów jest np-zupełne, tak jest Boolean-formula_1-spełnialność.

Wiemy, że 3-kolorowanie Wykresów jest np-zupełne; jednak historycznie wiemy, że najpierw pokazując np-kompletność spełnialności boolean-circuit-satisfiability, a następnie redukując to do 3-kolorystyka(zamiast na odwrót).