sprawdzanie jest łatwiejsze niż znajdowanie?
znalezienie rozwiązania problemu powinno być trudniejsze niż sprawdzenie, czy rozwiązanie jest poprawne. To wydaje się oczywiste, jeśli kiedykolwiek rozwiązałeś zagadkę sudoku, rozwiązałeś kostkę Rubika lub grałeś w szachy. Ale to stwierdzenie, jakkolwiek intuicyjnie wyglądające, prowadzi nas bezpośrednio do jednego z najgłębszych matematycznych pytań stawianych przez naszą cywilizację.
niedeterministyczne problemy czasu wielomianowego (lub NP) to takie, w których można łatwo zweryfikować poprawną odpowiedź., Natomiast problemy czasu wielomianowego (lub P) to te
, w których znalezienie odpowiedzi jest łatwe. Jeśli możesz znaleźć odpowiedź, to sprawdziłeś, że jest poprawna, więc każdy problem w P jest również w NP. Mówimy, że P jest podklasą NP. Nie wiemy jednak, czy w NP jest jakiś konkretny problem, który nie jest w P, i to jest to, co nazywamy problemem P vs NP.
problem P vs NP jest jednym z najbardziej centralnych nierozwiązanych problemów w matematyce i informatyce teoretycznej. Istnieje nawet Clay Millennium Prize oferujący milion dolarów za jego rozwiązanie., Jednak prawdopodobnie są o wiele łatwiejsze sposoby, aby stać się milionerem niż rozwiązywanie P vs NP!
ostatnio pojawił się szum, gdy ktoś chciał go rozwiązać na arXiv, chociaż szybko znaleziono lukę w dowodzie. Biorąc pod uwagę niedawne zainteresowanie tym problemem i jego centralne miejsce w matematyce, omawiam go w tym tygodniu na blogu.
Sudoku
Jeśli otrzymasz wypełnioną łamigłówkę Sudoku w gazecie, możesz wrzucić ją do kosza. Ale jeśli chcesz, możesz skanować wiersze, kolumny i komórki 3 x 3, aby powiedzieć, że jest to poprawne rozwiązanie: każda z 1 , 2,…, 9 musi wystąpić dokładnie raz., Jest to analogiczne do NP, ponieważ stosunkowo łatwo jest sprawdzić, czy rozwiązanie jest poprawne.
jednak, jeśli dam ci częściowo wypełnioną łamigłówkę Sudoku, może być trudno znaleźć rozwiązanie. To jest radość i wyzwanie tego rodzaju układanki. Więc bycie w NP nie od razu wydaje się sugerować problem ma łatwe do znalezienia rozwiązania. Ta intuicja leży u podstaw problemu P vs NP.
precyzyjne sformułowanie
aby dokładniej zrozumieć P i NP, musimy lepiej zrozumieć algorytmy i zmierzyć ich prędkość. Problemy pojawiają się przy pewnych stałych wejściach i wyjściach albo tak, albo nie. Wejście jest daną długością, powiedzmy n, gdzie n jest dodatnią liczbą całkowitą. Reprezentuje liczbę bitów potrzebnych do wyrażenia wejścia. Algorytm to metoda lub procedura rozwiązywania problemu. Algorytmy dostarczają instrukcje na każdym etapie obliczeń i muszą je zakończyć., Kroki mogą być sekundami, milisekundami lub innymi ustalonymi interwałami Czasu, które zależą od problemu.
złożoność problemu jest minimalnym czasem pracy wszystkich możliwych algorytmów rozwiązujących problem jako funkcja długości wejścia. Innymi słowy, mierzy, ile czasu zajmuje rozwiązanie problemu z najszybszym algorytmem, ale z najgorszym wynikiem.
problem jest rozwiązywalny w czasie wielomianowym, jeśli dany jest wkład długości n, jego złożoność jest ograniczona przez funkcję wielomianu nm dla pewnej nieujemnej liczby całkowitej m., Zbiór wszystkich problemów rozwiązywalnych w czasie wielomianowym jest oznaczony przez P.
bycie w P nie musi oznaczać, że problem jest wykonalny. Na przykład, jeśli do uruchomienia algorytmu potrzeba n1000 kroków, to będzie on beznadziejnie powolny nawet dla małych N. niedeterministyczne problemy wielomianowe (lub NP) są takie, w których można sprawdzić, czy odpowiedź tak jest poprawna w czasie wielomianowym.
np-twardość
problem jest np–twardość, jeśli algorytm wielomianu czasu dla niego implikuje algorytm wielomianu czasu dla każdego problemu w NP. Stąd, jeśli problem np-hard był w P, to P = NP., Problemy np-hard są co najmniej tak trudne jak każdy problem w NP. Problem np-zupełny to taki, który jest np-twardy i w NP.
klasycznym problemem np-zupełnym jest znalezienie cyklu Hamiltona. W tym celu Załóżmy, że mamy sieć miast połączonych drogami. Problem polega na tym, aby odwiedzić każde miasto za pomocą dróg (nie samoloty dozwolone!) i wrócić do początku. Wydaje się to łatwe dla niewielkiej liczby miast, ale jeśli dostali setki z nich, to staje się trudne., Znane są tysiące innych takich np-zupełnych problemów występujących w teorii grafów, teorii liczb, geometrii i innych dziedzinach matematyki i Informatyki.
Jaka jest odpowiedź?
gdybym miał obstawiać, to założyłbym, że P nie równa się NP i myślę, że większość ekspertów by się z tym zgodziła. Musielibyśmy być strasznie głupi, żeby nie widzieć, że wszystkie tysiące np-zupełnych problemów nie mają algorytmu czasu wielomianowego. Ale jako gatunek, głupi jest naszą domyślną pozycją, więc nikt nie może powiedzieć, jaka jest odpowiedź ze 100% pewnością.,
interesujące jest to, że problem P vs NP wskazuje na to, jak ograniczone jest nasze zrozumienie w udowodnieniu, że niektóre problemy nie mają szybkich rozwiązań. Jest to część większego tematu w dziedzinie teorii złożoności obliczeniowej, która bada dziesiątki innych klas złożoności. Sprawdź Zoo złożoności, aby zapoznać się z listą tych klas. W większości jest otwarty na pokazanie różnych (często egzotycznie brzmiących) klas złożoności, które są odpowiednimi podklasami siebie nawzajem. Na przykład nie wiadomo, czy NL jest właściwą podklasą P i nie wiemy, czy FPT jest właściwą podklasą W.,
niezależnie od jego prawdziwości, problem P vs NP prawdopodobnie pozostanie otwarty przez jakiś czas. Jeśli nie zostanie udowodnione, że P = NP, Sudoku pozostaje bezpieczne.
Anthony Bonato