Problem P kontra NP - P versus NP problem

Nierozwiązany problem w informatyce :

Jeśli rozwiązanie problemu jest łatwe do sprawdzenia pod kątem poprawności, czy problem musi być łatwy do rozwiązania?

Problem P kontra NP jest głównym nierozwiązanym problemem w informatyce . Pyta, czy każdy problem, którego rozwiązanie można szybko zweryfikować, da się również szybko rozwiązać.

Użyty powyżej nieformalny termin szybko , oznacza istnienie algorytmu rozwiązującego zadanie, które działa w czasie wielomianowym , tak że czas wykonania zadania różni się jako funkcja wielomianowa od wielkości danych wejściowych do algorytmu (w przeciwieństwie do powiedzmy, czas wykładniczy ). Ogólna klasa pytań, na które jakiś algorytm może udzielić odpowiedzi w czasie wielomianowym, to „ P ” lub „ klasa P ”. W przypadku niektórych pytań nie ma znanego sposobu na szybkie znalezienie odpowiedzi, ale jeśli otrzyma się informację pokazującą, jaka jest odpowiedź, można ją szybko zweryfikować. Klasa pytań, na które można zweryfikować odpowiedź w czasie wielomianowym, to NP , co oznacza „niedeterministyczny czas wielomianowy”.

Odpowiedź na pytanie P versus NP określiłaby, czy problemy, które można zweryfikować w czasie wielomianowym, można również rozwiązać w czasie wielomianowym. Jeśli okaże się, że P ≠ NP, co jest powszechnie uważane, oznaczałoby to, że istnieją problemy w NP, które są trudniejsze do obliczenia niż zweryfikowania: nie można ich rozwiązać w czasie wielomianowym, ale odpowiedź można zweryfikować w czasie wielomianowym .

Problem ten jest przez wielu uważany za najważniejszy otwarty problem w informatyce . Oprócz bycia ważnym problemem w teorii obliczeniowej , dowód w obie strony miałby głębokie implikacje dla matematyki, kryptografii , badań algorytmicznych, sztucznej inteligencji , teorii gier , przetwarzania multimediów, filozofii , ekonomii i wielu innych dziedzin.

Jest to jeden z siedmiu problemów związanych z Nagrodą Milenijną, wybranych przez Clay Mathematics Institute , z których każdy niesie nagrodę w wysokości 1 000 000 USD za pierwsze poprawne rozwiązanie.

Przykład

Rozważ Sudoku , grę, w której gracz otrzymuje częściowo wypełnioną siatkę liczb i próbuje wypełnić siatkę zgodnie z pewnymi zasadami. Biorąc pod uwagę niekompletną siatkę Sudoku dowolnej wielkości, czy istnieje co najmniej jedno rozwiązanie prawne? Każde zaproponowane rozwiązanie jest łatwo weryfikowane, a czas na sprawdzenie rozwiązania rośnie powoli (wielomianowo) w miarę powiększania się siatki. Jednak wszystkie znane algorytmy znajdowania rozwiązań wymagają, w przypadku trudnych przykładów, czasu, który rośnie wykładniczo wraz ze wzrostem siatki. Tak więc Sudoku jest w NP (szybko sprawdzalne), ale nie wydaje się być w P (szybko do rozwiązania). Tysiące innych problemów wydaje się być podobnych, ponieważ są szybkie do sprawdzenia, ale powolne do rozwiązania. Naukowcy wykazali, że wiele problemów w NP ma tę dodatkową właściwość, że szybkie rozwiązanie dowolnego z nich może być użyte do zbudowania szybkiego rozwiązania dowolnego innego problemu w NP, właściwość zwaną NP-zupełnością . Dziesięciolecia poszukiwań nie przyniosły szybkiego rozwiązania żadnego z tych problemów, więc większość naukowców podejrzewa, że ​​żadnego z tych problemów nie da się szybko rozwiązać. To jednak nigdy nie zostało udowodnione.

Historia

Dokładne sformułowanie problemu P kontra NP zostało wprowadzone w 1971 roku przez Stephena Cooka w jego przełomowym artykule „Złożoność procedur dowodzenia twierdzenia” (i niezależnie przez Leonida Levina w 1973 roku).

Chociaż problem P kontra NP został formalnie zdefiniowany w 1971 r., istniały wcześniejsze wyobrażenia o związanych z nim problemach, trudnościach dowodu i potencjalnych konsekwencjach. W 1955 roku matematyk John Nash napisał list do NSA , w którym spekulował, że złamanie wystarczająco złożonego kodu wymaga wykładniczego czasu w długości klucza. Gdyby zostało to udowodnione (a Nash był odpowiednio sceptyczny), to sugerowałoby to, co obecnie nazywa się P ≠ NP, ponieważ proponowany klucz można łatwo zweryfikować w czasie wielomianowym. Kolejna wzmianka o podstawowym problemie pojawiła się w liście Kurta Gödla z 1956 roku do Johna von Neumanna . Gödel zapytał, czy dowodzenie twierdzeń (obecnie znane jako współ-NP-zupełne ) można rozwiązać w czasie kwadratowym lub liniowym i wskazał jedną z najważniejszych konsekwencji — że jeśli tak, to odkrywanie dowodów matematycznych można by zautomatyzować.

Kontekst

Związek między klasami złożoności P i NP badany jest w teorii złożoności obliczeniowej , części teorii obliczeń zajmującej się zasobami wymaganymi podczas obliczeń do rozwiązania danego problemu. Najczęstsze zasoby to czas (ilość kroków potrzebnych do rozwiązania problemu) i miejsce (ilość pamięci potrzebnej do rozwiązania problemu).

W takiej analizie wymagany jest model komputera, dla którego należy analizować czas. Zazwyczaj takie modele zakładają, że komputer jest deterministyczny (biorąc pod uwagę obecny stan komputera i wszelkie dane wejściowe, jest tylko jedna możliwa akcja, którą może wykonać komputer) i sekwencyjny (wykonuje działania jedna po drugiej).

W tej teorii klasa P składa się ze wszystkich problemów decyzyjnych (zdefiniowanych poniżej ), które można rozwiązać na deterministycznej maszynie sekwencyjnej w czasie, który jest wielomianem wielkości danych wejściowych; klasa NP obejmuje wszystkie te problemy decyzyjne, których pozytywne rozwiązania można zweryfikować w czasie wielomianowym, mając odpowiednią informację, lub równoważnie, których rozwiązanie można znaleźć w czasie wielomianowym na maszynie niedeterministycznej . Oczywiście P NP. Prawdopodobnie największe otwarte pytanie w informatyce teoretycznej dotyczy relacji między tymi dwiema klasami:

Czy P jest równe NP?

Od 2002 roku William Gasarch przeprowadził trzy sondaże badaczy dotyczące tej i pokrewnych kwestii. Rośnie pewność, że P ≠ NP – w 2019 r. 88% uważało P NP, w przeciwieństwie do 83% w 2012 r. i 61% w 2002 r. W przypadku ograniczenia do ekspertów odpowiedzi z 2019 r. stały się dla 99% przekonaniem o P NP. Sondaże te nie sugerują niczego o tym, czy P=NP jest prawdziwe, jak stwierdził sam Gasarch: „Nie zbliża nas to ani do rozwiązania P=?NP, ani do wiedzy, kiedy zostanie rozwiązane, ale stara się być obiektywny raport o subiektywnej opinii tej epoki.”

NP-zupełność

Diagram Eulera dla zadań P , NP , NP-zupełnych i NP-trudnych (z wyłączeniem języka pustego i jego dopełnienia, które należą do P, ale nie są NP-zupełne)

Aby zaatakować pytanie P = NP, pojęcie NP-zupełności jest bardzo przydatne. Problemy NP-zupełne to zbiór problemów, do których każdy inny problem NP można zredukować w czasie wielomianu i którego rozwiązanie nadal można zweryfikować w czasie wielomianu. Oznacza to, że każdy problem NP może zostać przekształcony w dowolny problem NP-zupełny. Nieformalnie problem NP-zupełny to problem NP, który jest co najmniej tak „trudny” jak każdy inny problem w NP.

Problemy NP-trudne to te co najmniej tak trudne, jak problemy NP; tj. wszystkie problemy NP można zredukować (w czasie wielomianowym) do nich. Problemy NP-trudne nie muszą być w NP; tzn. nie muszą mieć rozwiązań sprawdzalnych w czasie wielomianowym.

Na przykład, problem spełnialności Boole'a jest NP-zupełny przez twierdzenie Cooka-Levina , więc każdy przypadek dowolnego problemu w NP może być przekształcony mechanicznie w instancję problemu spełnialności Boole'a w czasie wielomianowym. Problem spełnialności logicznej jest jednym z wielu takich problemów NP-zupełnych. Jeśli jakikolwiek problem NP-zupełny jest w P, to wynikałoby z tego, że P = NP. Wykazano jednak, że wiele ważnych problemów jest NP-zupełnych i nie jest znany żaden szybki algorytm dla żadnego z nich.

Na podstawie samej definicji nie jest oczywiste, że istnieją problemy NP-zupełne; jednak trywialny i wymyślony problem NP-zupełny można sformułować w następujący sposób: biorąc pod uwagę opis maszyny Turinga M, która gwarantuje zatrzymanie w czasie wielomianowym, czy istnieje dane wejściowe o rozmiarze wielomianowym, które M zaakceptuje? Jest w NP, ponieważ (biorąc pod uwagę dane wejściowe) łatwo jest sprawdzić, czy M akceptuje dane wejściowe, symulując M ; jest NP-zupełny, ponieważ weryfikator dla dowolnego konkretnego przypadku problemu w NP może być zakodowany jako maszyna czasu wielomianowego M, która przyjmuje rozwiązanie do weryfikacji jako dane wejściowe. Następnie pytanie, czy instancja jest instancją tak, czy nie, zależy od tego, czy istnieje prawidłowe dane wejściowe.

Pierwszym naturalnym problemem, który okazał się NP-zupełny, był problem spełnialności logicznej, znany również jako SAT. Jak wspomniano powyżej, jest to twierdzenie Cooka-Levina; jego dowód, że spełnialność jest NP-zupełna, zawiera szczegóły techniczne dotyczące maszyn Turinga, ponieważ odnoszą się one do definicji NP. Jednak po tym, jak udowodniono, że problem ten jest NP-zupełny, dowód przez redukcję dostarczył prostszego sposobu wykazania, że ​​wiele innych problemów jest również NP-zupełnych, w tym omawiana wcześniej gra Sudoku. W tym przypadku dowód pokazuje, że rozwiązanie Sudoku w czasie wielomianowym może być również użyte do uzupełnienia kwadratów łacińskich w czasie wielomianowym. To z kolei daje rozwiązanie problemu podziału grafów trójdzielnych na trójkąty, które można następnie wykorzystać do znalezienia rozwiązań dla specjalnego przypadku SAT znanego jako 3-SAT, który następnie zapewnia rozwiązanie dla ogólnej spełnialności logicznej. Zatem rozwiązanie Sudoku w czasie wielomianowym prowadzi, poprzez serię przekształceń mechanicznych, do rozwiązania w czasie wielomianowym spełnialności, które z kolei może być użyte do rozwiązania dowolnego innego problemu NP w czasie wielomianowym. Wykorzystując takie transformacje, ogromna klasa pozornie niepowiązanych problemów jest redukowalna do siebie i jest w pewnym sensie „tym samym problemem”.

Trudniejsze problemy

Chociaż nie wiadomo, czy P = NP, znane są problemy poza P. Tak jak klasa P jest zdefiniowana w kategoriach wielomianowego czasu działania, klasa EXPTIME jest zbiorem wszystkich problemów decyzyjnych, które mają wykładniczy czas działania. Innymi słowy, każdy problem w EXPTIME jest rozwiązywalny przez deterministyczną maszynę Turinga w czasie O (2 p ( n ) ), gdzie p ( n ) jest funkcją wielomianową n . Problem decyzyjny jest EXPTIME-kompletny, jeśli znajduje się w EXPTIME, a każdy problem w EXPTIME ma redukcję wielomianową wiele-jeden . Wiadomo, że wiele problemów jest zakończonych EXPTIME. Ponieważ można wykazać, że P ≠ EXPTIME, problemy te są poza P, a więc wymagają więcej niż czasu wielomianowego. W rzeczywistości, według twierdzenia o hierarchii czasowej , nie można ich rozwiązać w czasie znacznie krótszym niż czas wykładniczy. Przykłady obejmują znalezienie idealnej strategii dla pozycji szachowych na planszy N × N i podobne problemy w innych grach planszowych.

Problem rozstrzygnięcia prawdziwości wypowiedzi w arytmetyce presburgerskiej wymaga jeszcze więcej czasu. Fischer i Rabin udowodnili w 1974 roku, że każdy algorytm, który decyduje o prawdziwości twierdzeń Presburgera o długości n, ma czas działania przynajmniej dla pewnej stałej c . W związku z tym wiadomo, że problem wymaga więcej niż wykładniczego czasu wykonywania. Jeszcze trudniejsze są nierozstrzygalne problemy , takie jak problem zatrzymania . Nie mogą być one całkowicie rozwiązane przez żaden algorytm, w tym sensie, że dla każdego konkretnego algorytmu istnieje co najmniej jedno wejście, dla którego algorytm ten nie da prawidłowej odpowiedzi; albo da niewłaściwą odpowiedź, skończy się bez podania rozstrzygającej odpowiedzi, albo w inny sposób będzie trwać wiecznie, nie dając w ogóle żadnej odpowiedzi.

Możliwe jest również rozważenie pytań innych niż problemy decyzyjne. Jedna z takich klas, składająca się z liczenia problemów, nazywa się #P : podczas gdy problem NP pyta "Czy są jakieś rozwiązania?", odpowiadający mu problem #P pyta "Ile jest rozwiązań?" Oczywiście, problem #P musi być co najmniej tak trudny, jak odpowiadający mu problem NP, ponieważ liczba rozwiązań natychmiast mówi, czy istnieje co najmniej jedno rozwiązanie, jeśli liczba jest większa od zera. Co zaskakujące, niektóre problemy #P, które uważa się za trudne, odpowiadają łatwym (na przykład liniowym) problemom P. W przypadku tych problemów bardzo łatwo jest stwierdzić, czy istnieją rozwiązania, ale uważa się, że bardzo trudno jest powiedzieć, ile. Wiele z tych problemów to #P-zupełne , a zatem należą do najtrudniejszych problemów w #P, ponieważ wielomianowe rozwiązanie każdego z nich pozwoliłoby na wielomianowe rozwiązanie wszystkich innych problemów #P.

Problemy w NP, o których nie wiadomo, czy są w P lub NP-zupełne

W 1975 r. Richard E. Ladner wykazał, że jeśli P ≠ NP, to istnieją problemy w NP, które nie są ani w P, ani w NP-zupełne. Takie problemy nazywane są problemami NP-pośrednimi. Problemem wykres Izomorfizm The dyskretnych problemem logarytm i błąd całkowitą faktoryzacji przykłady problemów, uważa się, NP-półproduktu. Są to jedne z niewielu problemów NP, o których nie wiadomo, czy występują w P lub są NP-zupełne.

Problem izomorfizmu grafów to problem obliczeniowy określający, czy dwa skończone grafyizomorficzne . Ważnym nierozwiązanym problemem w teorii złożoności jest to, czy problem izomorfizmu grafów ma charakter P, NP-zupełny, czy NP-pośredni. Odpowiedź nie jest znana, ale uważa się, że problem nie jest przynajmniej NP-zupełny. Jeśli izomorfizm grafu jest NP-zupełny, wielomianowa hierarchia czasowa zapada się do drugiego poziomu. Ponieważ powszechnie uważa się, że hierarchia wielomianowa nie zapada się do żadnego skończonego poziomu, uważa się, że izomorfizm grafu nie jest NP-zupełny. Najlepszy algorytm dla tego problemu, dzięki László Babai , działa w czasie quasi-wielomianowym .

Problemem całkowitą faktoryzacji jest obliczeniowa problemu określania czynniki pierwsze danej liczby całkowitej. Sformułowany jako problem decyzyjny, jest to problem decydowania, czy dane wejściowe mają współczynnik mniejszy niż k . Nie jest znany żaden wydajny algorytm faktoryzacji liczb całkowitych, a fakt ten stanowi podstawę kilku nowoczesnych systemów kryptograficznych, takich jak algorytm RSA . Problem faktoryzacji liczb całkowitych dotyczy NP i współ-NP (a nawet UP i współ-UP). Jeśli problem jest NP-zupełny, wielomianowa hierarchia czasu upadnie do pierwszego poziomu (tj. NP = co-NP). Najbardziej znanym algorytmem faktoryzacji liczb całkowitych jest ogólne sito pola liczbowego , które zajmuje oczekiwany czas

rozłożyć na czynniki n- bitową liczbę całkowitą. Jednak najlepiej znany algorytm kwantowy dla tego problemu, algorytm Shora , działa w czasie wielomianowym, chociaż nie wskazuje, gdzie leży problem w odniesieniu do niekwantowych klas złożoności .

Czy P oznacza „łatwy”?

Wykres przedstawia czas wykonania w zależności od rozmiaru problemu dla problemu plecakowego najnowocześniejszego, wyspecjalizowanego algorytmu. Kwadratowy dopasowanie sugeruje algorytmiczne problem złożoności O ((log ( n )) 2 ).

Wszystkie powyższe rozważania zakładają, że P oznacza „łatwe”, a „nie w P” oznacza „trudne”, założenie znane jako teza Cobhama . Jest to powszechne i dość dokładne założenie w teorii złożoności; ma jednak pewne zastrzeżenia.

Po pierwsze, w praktyce nie zawsze jest to prawdą. Teoretyczny algorytm wielomianowy może mieć bardzo duże stałe współczynniki lub wykładniki, co czyni go niepraktycznym. Na przykład problem decydowania, czy graf G zawiera H jako minor , gdzie H jest ustalone, można rozwiązać w czasie wykonywania O ( n 2 ), gdzie n jest liczbą wierzchołków w G . Jednak duża notacja O ukrywa stałą, która zależy superwykładniczo od H . Stała jest większa niż (przy użyciu notacji Knutha ze strzałką w górę ), a gdzie h jest liczbą wierzchołków w H .

Z drugiej strony, nawet jeśli okaże się, że problem jest NP-zupełny i nawet jeśli P ≠ NP, nadal mogą istnieć skuteczne podejścia do praktycznego rozwiązania problemu. Istnieje wiele algorytmów dla problemów NP-zupełny, takich jak problem plecakowy , do problemu komiwojażera i problem spełnialności , że można rozwiązać do optymalności wielu przypadkach rzeczywistych w rozsądnym czasie. Empiryczna złożoność przeciętnego przypadku (czas vs rozmiar problemu) takich algorytmów może być zaskakująco niska. Przykładem jest algorytm simpleks w programowaniu liniowym , który w praktyce sprawdza się zaskakująco dobrze; pomimo wykładniczej złożoności czasu najgorszego przypadku , działa na równi z najlepszymi znanymi algorytmami czasu wielomianowego.

Wreszcie istnieją rodzaje obliczeń, które nie są zgodne z modelem maszyny Turinga, w którym zdefiniowano P i NP, takie jak obliczenia kwantowe i algorytmy randomizowane .

Powody, by sądzić P ≠ NP lub P = NP

Cook ponownie przedstawia problem w P VERSUS NP PROBLEM w następujący sposób: Czy P = NP ? . Według sondaży większość informatyków uważa, że ​​P ≠ NP. Kluczowym powodem tego przekonania jest to, że po dziesięcioleciach studiowania tych problemów nikomu nie udało się znaleźć algorytmu czasu wielomianowego dla żadnego z ponad 3000 ważnych znanych problemów NP-zupełnych (patrz Lista problemów NP-zupełnych ). Algorytmy te były poszukiwane na długo przed zdefiniowaniem pojęcia NP-zupełności ( 21 problemów NP-zupełnych Karpa , wśród pierwszych znalezionych, wszystkie były dobrze znanymi problemami istniejącymi w czasie, gdy wykazano, że są NP-zupełne). Ponadto wynik P = NP sugerowałby wiele innych zaskakujących wyników, które obecnie uważa się za fałszywe, takich jak NP = co-NP i P = PH .

Intuicyjnie argumentuje się również, że istnienie problemów, które są trudne do rozwiązania, ale dla których rozwiązania są łatwe do zweryfikowania, pasuje do rzeczywistych doświadczeń.

Gdyby P = NP, świat byłby zupełnie innym miejscem, niż zwykle zakładamy. Nie byłoby żadnej szczególnej wartości w „kreatywnych skokach”, żadnej fundamentalnej luki między rozwiązaniem problemu a rozpoznaniem rozwiązania po jego znalezieniu.

Z drugiej strony niektórzy badacze uważają, że istnieje zbytnia pewność siebie w wierze P ≠ NP i że badacze powinni również zbadać dowody na P = NP. Na przykład w 2002 r. padły te oświadczenia:

Głównym argumentem przemawiającym za P ≠ NP jest całkowity brak fundamentalnego postępu w obszarze wyczerpujących poszukiwań. To moim zdaniem bardzo słaby argument. Przestrzeń algorytmów jest bardzo duża i jesteśmy dopiero na początku jej eksploracji. […] Rozwiązanie Wielkiego Twierdzenia Fermata pokazuje również, że bardzo proste pytania mogą być rozwiązane tylko przez bardzo głębokie teorie.

Przywiązanie do spekulacji nie jest dobrym przewodnikiem w planowaniu badań. W każdym problemie należy zawsze próbować w obie strony. Uprzedzenia sprawiły, że sławni matematycy nie potrafili rozwiązać słynnych problemów, których rozwiązanie było sprzeczne z ich oczekiwaniami, mimo że opracowali wszystkie wymagane metody.

Konsekwencje rozwiązania

Jednym z powodów, dla których problem przyciąga tak wiele uwagi, są konsekwencje kilku możliwych odpowiedzi. Każdy kierunek rozwiązania ogromnie rozwinąłby teorię i być może miałby również ogromne konsekwencje praktyczne.

P = NP

Dowód na to, że P = NP może mieć oszałamiające konsekwencje praktyczne, jeśli doprowadzi do skutecznych metod rozwiązywania niektórych ważnych problemów w NP. Potencjalne konsekwencje, zarówno pozytywne, jak i negatywne, wynikają z tego, że różne problemy NP-zupełności mają fundamentalne znaczenie w wielu dziedzinach.

Jest również bardzo możliwe, że dowód nie prowadziłby do praktycznych algorytmów dla problemów NP-zupełnych. Sformułowanie problemu nie wymaga, aby wielomian graniczny był mały lub nawet dokładnie znany. Niekonstruktywne dowodu może pokazać istnieje rozwiązanie bez określania zarówno algorytm je uzyskać lub specyficzny związane. Nawet jeśli dowód jest konstruktywny, pokazując jawny wielomian graniczny i szczegóły algorytmiczne, jeśli wielomian nie jest bardzo niskiego rzędu, algorytm może nie być wystarczająco wydajny w praktyce. W tym przypadku wstępny dowód zainteresowałby głównie teoretyków, ale wiedza, że ​​możliwe są rozwiązania wielomianowe w czasie, z pewnością zachęciłaby do poszukiwania lepszych (i być może praktycznych) metod ich osiągnięcia.

Przykładem pola, które może zostać wykorzenione przez rozwiązanie pokazujące P = NP, jest kryptografia , która opiera się na trudnościach pewnych problemów. Konstruktywne i wydajne rozwiązanie problemu NP-zupełnego, takiego jak 3-SAT , złamałoby większość istniejących kryptosystemów, w tym:

  • Istniejące implementacje kryptografii klucza publicznego , stanowiące podstawę wielu nowoczesnych aplikacji zabezpieczających, takich jak bezpieczne transakcje finansowe w Internecie.
  • Szyfry symetryczne, takie jak AES lub 3DES , używane do szyfrowania danych komunikacyjnych.
  • Hasz kryptograficzny , który leży u podstaw kryptowalut blockchain, takich jak Bitcoin , i jest używany do uwierzytelniania aktualizacji oprogramowania. W przypadku tych zastosowań problem ze znalezieniem obrazu wstępnego, który miesza do określonej wartości, musi być trudny, aby był użyteczny, a najlepiej powinien wymagać czasu wykładniczego. Jeśli jednak P = NP, to znalezienie wstępnego obrazu M można przeprowadzić w czasie wielomianowym, poprzez redukcję do SAT.

Należałoby je zmodyfikować lub zastąpić rozwiązaniami teoretycznie bezpiecznymi dla informacji, które nie są z natury oparte na nierównoważności P-NP.

Z drugiej strony, uczynienie wykonalnymi wielu obecnie matematycznie nierozwiązywalnych problemów pociąga za sobą ogromne pozytywne konsekwencje. Na przykład wiele problemów w badaniach operacyjnych jest NP-zupełnych, takich jak niektóre typy programowania liczb całkowitych i problem komiwojażera . Skuteczne rozwiązania tych problemów miałyby ogromne implikacje dla logistyki. Wiele innych ważnych problemów, takich jak pewne problemy w przewidywaniu struktury białka , jest również NP-zupełne; gdyby te problemy były skutecznie rozwiązane, mogłoby to pobudzić znaczny postęp w naukach przyrodniczych i biotechnologii.

Ale takie zmiany mogą blednąć w porównaniu z rewolucją, jaką w samej matematyce spowodowałaby wydajna metoda rozwiązywania problemów NP-zupełnych. Gödel, w swoich wczesnych przemyśleniach na temat złożoności obliczeniowej, zauważył, że metoda mechaniczna, która mogłaby rozwiązać każdy problem, zrewolucjonizowałaby matematykę:

Gdyby rzeczywiście istniała maszyna z φ(n) ∼ k ⋅ n (lub nawet ∼ k ⋅ n 2 ), miałoby to największe znaczenie. Mianowicie, oczywiście oznaczałoby to, że pomimo nierozstrzygalności problemu Entscheidungs , pracę umysłową matematyka nad pytaniami typu „tak-lub-nie” można by całkowicie zastąpić maszyną. W końcu należałoby po prostu wybrać liczbę naturalną n tak dużą, że gdy maszyna nie daje wyniku, nie ma sensu więcej zastanawiać się nad problemem.

Podobnie Stephen Cook (zakładając nie tylko dowód, ale praktycznie skuteczny algorytm)

... przekształciłoby matematykę, umożliwiając komputerowi znalezienie formalnego dowodu dowolnego twierdzenia, które ma dowód o rozsądnej długości, ponieważ dowody formalne można łatwo rozpoznać w czasie wielomianowym. Przykładowe problemy mogą równie dobrze obejmować wszystkie problemy związane z nagrodami CMI .

Matematycy zajmujący się badaniami naukowymi spędzają swoje kariery na próbach udowadniania twierdzeń, a odnalezienie niektórych dowodów po stwierdzeniu problemów zajęło dziesięciolecia, a nawet stulecia — na przykład udowodnienie ostatniego twierdzenia Fermata zajęło ponad trzy stulecia. Metoda, która gwarantuje znalezienie dowodów na twierdzenia, gdyby istniała „rozsądna” wielkość, zasadniczo zakończyłaby tę walkę.

Donald Knuth stwierdził, że doszedł do przekonania, że ​​P = NP, ale jest powściągliwy co do wpływu ewentualnego dowodu:

[...] jeśli wyobrazisz sobie liczbę M, która jest skończona, ale niewiarygodnie duża — jak powiedzmy liczba 10↑↑↑↑3 omówiona w moim artykule na temat „radzenia sobie ze skończonością” — to istnieje ogromna liczba możliwych algorytmów, które n M operacje bitowe, dodawanie lub przesuwanie na n danych bitach i naprawdę trudno uwierzyć, że wszystkie te algorytmy zawodzą. Moim głównym punktem jest jednak to, że nie wierzę, aby równość P = NP okazała się pomocna, nawet jeśli zostanie udowodniona, ponieważ taki dowód będzie prawie na pewno niekonstruktywny.

Schemat klas złożoności pod warunkiem, że P   NP. Istnienie problemów w obrębie NP, ale poza nimi zarówno P, jak i NP-zupełne, przy tym założeniu, zostało ustalone przez twierdzenie Ladnera .

P NP

Dowód, który wykazał, że P ≠ NP byłby pozbawiony praktycznych korzyści obliczeniowych dowodu, że P = NP, ale mimo to stanowiłby bardzo znaczący postęp w teorii złożoności obliczeniowej i dostarczyłby wskazówek dla przyszłych badań. Pozwoliłoby to na wykazanie w sposób formalny, że wielu powszechnych problemów nie da się skutecznie rozwiązać, tak aby uwaga badaczy mogła być skupiona na rozwiązaniach cząstkowych lub rozwiązaniach innych problemów. Ze względu na powszechną wiarę w P ≠ NP, znaczna część tego ukierunkowania badań już miała miejsce.

Również P ≠ NP nadal pozostawia otwartą przeciętną złożoność trudnych problemów w NP. Na przykład możliwe jest, że SAT w najgorszym przypadku wymaga czasu wykładniczego, ale prawie wszystkie losowo wybrane jego wystąpienia są skutecznie rozwiązywalne. Russell Impagliazzo opisał pięć hipotetycznych „światów”, które mogą wynikać z różnych możliwych rozwiązań problemu złożoności przeciętnego przypadku. Obejmują one od „Algorytmiki”, gdzie P = NP i problemy takie jak SAT można skutecznie rozwiązywać we wszystkich przypadkach, do „Kryptomanii”, gdzie P ≠ NP i generowanie trudnych przypadków problemów poza P jest łatwe, z trzema pośrednimi możliwościami odzwierciedlającymi różne możliwe rozkłady trudności w przypadkach problemów NP-trudnych. „Świat”, w którym P NP, ale wszystkie problemy w NP są wykonalne w przeciętnym przypadku, nazywa się w artykule „Heurystyką”. Princeton University warsztat w 2009 roku badał stan pięciu światów.

Wyniki dotyczące trudności dowodu

Chociaż sam problem P = NP pozostaje otwarty pomimo nagrody w wysokości miliona dolarów i ogromnej ilości dedykowanych badań, wysiłki mające na celu rozwiązanie tego problemu doprowadziły do ​​kilku nowych technik. W szczególności niektóre z najbardziej owocnych badań związanych z problemem P = NP polegały na wykazaniu, że istniejące techniki dowodowe nie są wystarczająco silne, aby odpowiedzieć na to pytanie, co sugeruje, że potrzebne są nowe podejścia techniczne.

Jako dodatkowy dowód na trudność problemu, zasadniczo wszystkie znane techniki dowodowe w teorii złożoności obliczeniowej podlegają jednej z następujących klasyfikacji, z których wiadomo, że każda z nich jest niewystarczająca do udowodnienia, że ​​P ≠ NP:

Klasyfikacja Definicja
Relatywizujące dowody Wyobraź sobie świat, w którym każdy algorytm może wysyłać zapytania do pewnego stałego podprogramu zwanego wyrocznią (czarna skrzynka, która może odpowiedzieć na ustalony zestaw pytań w stałym czasie, taka jak czarna skrzynka, która rozwiązuje dowolny problem komiwojażera w 1 kroku) , a czas działania wyroczni nie jest wliczany do czasu działania algorytmu. Większość dowodów (zwłaszcza klasycznych) stosuje się jednakowo w świecie z wyroczniami, niezależnie od tego, co robi wyrocznia. Dowody te nazywane są relatywizującymi . W 1975 roku Baker, Gill i Solovay wykazali, że P = NP w odniesieniu do niektórych wyroczni, podczas gdy P ≠ NP dla innych wyroczni. Ponieważ dowody relatywizujące mogą dowodzić tylko twierdzeń, które są jednolicie prawdziwe w odniesieniu do wszystkich możliwych wyroczni, pokazało to, że techniki relatywizujące nie mogą rozwiązać P = NP.
Naturalne dowody W 1993 roku Alexander Razborov i Steven Rudich zdefiniowali ogólną klasę technik dowodowych dla dolnych granic złożoności obwodów, zwanych dowodami naturalnymi . W tamtym czasie wszystkie znane wcześniej granice dolne obwodów były naturalne, a złożoność obwodów była uważana za bardzo obiecujące podejście do rozwiązania P = NP. Jednak Razborov i Rudich wykazali, że jeśli istnieją funkcje jednokierunkowe , to żadna metoda naturalnego dowodu nie jest w stanie odróżnić P i NP. Chociaż nigdy formalnie nie udowodniono istnienia funkcji jednokierunkowych, większość matematyków uważa, że ​​tak, a dowód ich istnienia byłby znacznie silniejszym stwierdzeniem niż P ≠ NP. Zatem jest mało prawdopodobne, aby same dowody naturalne mogły rozwiązać P = NP.
Algebryzacja dowodów Po wynikach Baker-Gill-Solovay, nowe nierelatywizowane techniki dowodowe zostały z powodzeniem wykorzystane do udowodnienia, że IP = PSPACE . Jednak w 2008 roku Scott Aaronson i Avi Wigderson wykazali, że główne narzędzie techniczne użyte w dowodzie IP = PSPACE, znane jako arytmetyzacja , było również niewystarczające do rozwiązania P = NP.

Bariery te są kolejnym powodem, dla którego problemy NP-zupełne są użyteczne: jeśli można wykazać algorytm wielomianowy dla problemu NP-zupełnego, to rozwiązałoby to problem P = NP w sposób nie wykluczony przez powyższe wyniki.

Bariery te doprowadziły również niektórych informatyków do zasugerowania, że ​​problem P kontra NP może być niezależny od standardowych systemów aksjomatów, takich jak ZFC (nie można ich w nich udowodnić ani obalić). Interpretacja wyniku niezależności może być taka, że ​​albo nie istnieje algorytm wielomianowy dla żadnego problemu NP-zupełnego, a takiego dowodu nie można skonstruować w (np.) ZFC, albo że mogą istnieć algorytmy wielomianowe dla problemów NP-zupełnych, ale nie można udowodnić w ZFC, że takie algorytmy są poprawne. Gdyby jednak można było wykazać za pomocą technik, o których obecnie wiadomo, że mają zastosowanie, że problemu nie da się rozstrzygnąć nawet przy znacznie słabszych założeniach rozszerzających aksjomaty Peano (PA) dla arytmetyki liczb całkowitych, to z konieczności istniałyby prawie algorytmy wielomianowe dla każdego problemu w NP. Dlatego, jeśli ktoś wierzy (jak większość teoretyków złożoności), że nie wszystkie problemy w NP mają wydajne algorytmy, to wynika z tego, że dowody niezależności przy użyciu tych technik nie mogą być możliwe. Dodatkowo wynik ten implikuje, że udowodnienie niezależności od PA lub ZFC przy użyciu obecnie znanych technik nie jest łatwiejsze niż udowodnienie istnienia wydajnych algorytmów dla wszystkich problemów w NP.

Twierdzone rozwiązania

Podczas gdy problem P kontra NP jest ogólnie uważany za nierozwiązany, wielu badaczy-amatorów i niektórzy zawodowi badacze domagają się rozwiązań. Gerhard J. Woeginger utrzymuje listę, która od 2016 r. zawiera 62 rzekome dowody P = NP, 50 dowodów P ≠ NP, 2 dowody, że problem jest niedowodliwy i jeden dowód, że jest nierozstrzygalny. Najwyraźniej co najmniej 53 z tych dowodów są błędne. Niektóre próby rozwiązania P w porównaniu z NP spotkały się z krótkim zainteresowaniem mediów, chociaż te próby zostały odrzucone.

Charakterystyki logiczne

Problem P = NP można przeformułować w kategoriach wyrażalnych pewnych klas zdań logicznych, w wyniku prac nad złożonością opisową .

Rozważ wszystkie języki o skończonych strukturach ze stałą sygnaturą, w tym liniową relację porządku . Następnie wszystkie takie języki w P mogą być wyrażone w logice pierwszego rzędu z dodatkiem odpowiedniego kombinatora najmniej ustalonego punktu . Faktycznie to, w połączeniu z porządkiem, pozwala na zdefiniowanie funkcji rekurencyjnych. Dopóki sygnatura zawiera co najmniej jeden predykat lub funkcję oprócz wyróżnionej relacji kolejności, tak że ilość miejsca zajęta do przechowywania takich skończonych struktur jest w rzeczywistości wielomianem w liczbie elementów w strukturze, to dokładnie charakteryzuje P.

Podobnie NP jest zbiorem języków dających się wyrazić w egzystencjalnej logice drugiego rzędu — to znaczy logice drugiego rzędu ograniczonej do wykluczenia uniwersalnej kwantyfikacji relacji, funkcji i podzbiorów. Języki w wielomianu hierarchii , PH , odpowiadają wszystkim logiki drugiego rzędu. Tak więc pytanie „czy P jest właściwym podzbiorem NP” można przeformułować jako „czy egzystencjalna logika drugiego rzędu jest w stanie opisać języki (o skończonych liniowo uporządkowanych strukturach z nietrywialną sygnaturą), których logika pierwszego rzędu z najmniejszą liczbą punktów stałych nie może?” . Słowo „egzystencjalny” można nawet usunąć z poprzedniej charakterystyki, ponieważ P = NP wtedy i tylko wtedy, gdy P = PH (ponieważ to pierwsze ustaliłoby, że NP = współ-NP, co z kolei implikuje, że NP = PH).

Algorytmy wielomianowe

Żaden algorytm dla żadnego problemu NP-zupełnego nie działa w czasie wielomianowym. Istnieją jednak algorytmy znane z problemów NP-zupełnych o własności, że jeśli P = NP, to algorytm działa w czasie wielomianowym na akceptowaniu instancji (chociaż z ogromnymi stałymi, co czyni algorytm niepraktycznym). Jednak te algorytmy nie kwalifikują się jako czas wielomianowy, ponieważ ich czas działania przy odrzucaniu wystąpień nie jest wielomianem. Poniższy algorytm, dzięki Levinowi (bez cytowania), jest takim przykładem poniżej. Prawidłowo akceptuje język NP-zupełny SUBSET-SUM . Działa w czasie wielomianowym na wejściach, które są w SUBSET-SUM wtedy i tylko wtedy, gdy P = NP:

// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
  FOR M = 1...K
    Run program number M for K steps with input S
    IF the program outputs a list of distinct integers
      AND the integers are all in S
      AND the integers sum to 0
    THEN
      OUTPUT "yes" and HALT

Jeśli i tylko wtedy, gdy P = NP, to jest to algorytm wielomianowy akceptujący język NP-zupełny. „Akceptowanie” oznacza, że ​​daje odpowiedzi „tak” w czasie wielomianowym, ale może działać w nieskończoność, gdy odpowiedź brzmi „nie” (znany również jako półalgorytm ).

Ten algorytm jest niezwykle niepraktyczny, nawet jeśli P = NP. Jeśli najkrótszy program, który może rozwiązać SUBSET-SUM w czasie wielomianowym, ma długość b bitów, powyższy algorytm najpierw spróbuje co najmniej 2 b − 1 innych programów.

Formalne definicje

P i NP

Mówiąc koncepcyjnie, problem decyzyjny to problem, który przyjmuje jako dane wejściowe jakiś łańcuch w nad alfabetem Σ i daje w wyniku „tak” lub „nie”. Jeśli istnieje algorytm (powiedzmy, maszyna Turinga lub program komputerowy z nieograniczoną pamięcią), który może wygenerować poprawną odpowiedź dla dowolnego ciągu wejściowego o długości n w co najwyżej cn k krokach, gdzie k i c są stałymi niezależnymi od ciągu wejściowego , wtedy mówimy, że problem można rozwiązać w czasie wielomianowym i umieszczamy go w klasie P. Formalnie P jest zdefiniowany jako zbiór wszystkich języków, które mogą być rozstrzygnięte przez deterministyczną maszynę Turinga w czasie wielomianowym. To jest,

gdzie

a deterministyczna maszyna Turinga w czasie wielomianowym jest deterministyczną maszyną Turinga M, która spełnia następujące dwa warunki:

  1. M zatrzymuje się na wszystkich wejściach w i
  2. istnieje takie, że , gdzie O odnosi się do notacji dużego O i

NP można zdefiniować podobnie za pomocą niedeterministycznych maszyn Turinga (tradycyjny sposób). Jednak nowoczesnym podejściem do definiowania NP jest wykorzystanie koncepcji certyfikatu i weryfikatora . Formalnie NP jest zdefiniowany jako zbiór języków w skończonym alfabecie, które mają weryfikator działający w czasie wielomianowym, gdzie pojęcie „weryfikatora” jest zdefiniowane w następujący sposób.

Niech L będzie językiem nad skończonym alfabetem, Σ.

L ∈ NP wtedy i tylko wtedy, gdy istnieje relacja binarna i dodatnia liczba całkowita k takie, że spełnione są dwa warunki:

  1. Dla wszystkich , takie , że ( x , y ) ∈ R i ; oraz
  2. język na to rozstrzygalne przez deterministycznej maszyny Turinga w czasie wielomianowym.

Urządzenie Turingowi decyduje L R jest nazywany weryfikator dla L i y takie, że ( x , y ) ∈ R nazywa się zaświadczenie członkostwa w x w L .

Ogólnie rzecz biorąc, weryfikator nie musi być wielomianowy. Jednak aby L było w NP, musi istnieć weryfikator działający w czasie wielomianowym.

Przykład

Pozwolić

Oczywiście pytanie, czy dany x jest złożeniem, jest równoznaczne z pytaniem, czy x należy do ZŁOŻONEGO. Można wykazać, że COMPOSITE ∈ NP sprawdzając, czy spełnia powyższą definicję (jeśli utożsamiamy liczby naturalne z ich reprezentacjami binarnymi).

COMPOSITE zdarza się również w P, co potwierdza wynalezienie testu pierwszości AKS .

NP-zupełność

Istnieje wiele równoważnych sposobów opisywania NP-zupełności.

Niech L będzie językiem nad skończonym alfabetem Σ.

L jest NP-zupełne wtedy i tylko wtedy, gdy spełnione są następujące dwa warunki:

  1. L NP; oraz
  2. dowolne L w NP jest wielomianowo redukowalne do L (zapisane jako ), gdzie wtedy i tylko wtedy, gdy spełnione są następujące dwa warunki:
    1. Istnieje f  : Σ* → Σ* takie, że dla wszystkich w w Σ* mamy: ; oraz
    2. istnieje wielomianowa maszyna Turinga, która zatrzymuje się z f ( w ) na swojej taśmie na dowolnym wejściu w .

Alternatywnie, jeśli L NP i istnieje inny problem NP-zupełny, który można zredukować w czasie wielomianowym do L , wtedy L jest NP-zupełny. Jest to powszechny sposób na udowodnienie, że jakiś nowy problem jest NP-zupełny.

Kultura popularna

Film Travelling Salesman reżysera Timothy'ego Lanzone'a to historia czterech matematyków zatrudnionych przez rząd USA do rozwiązania problemu „P kontra NP”.

W szóstym odcinku The Simpsons ' siódmego sezonu " Treehouse of Horror VI ", równanie P = NP jest widoczne zaraz po Homer przypadkowo potyka się "trzeciego wymiaru".

W drugim odcinku sezonu 2 Elementary , „Rozwiąż dla X” obraca się wokół Sherlocka i Watsona badających morderstwa matematyków, którzy próbowali rozwiązać P z NP.

Zobacz też

Uwagi

Bibliografia

Źródła

Dalsza lektura

Zewnętrzne linki