Problem P=NP rozwiązany?
Niewykluczone, że rozwiązano jedną z najważniejszych zagadek informatyki. Przed kilkoma dniami Vinay Deolalikar, matematyk z HP Labs udostępnił dokument zatytułowny "P≠NP". Jeśli wyliczenia Deolalikara okażą się prawidłowe, będzie to oznaczało, że komputery, niezależnie od ich mocy obliczeniowej, nie poradzą sobie z wieloma stawianymi przed nimi zadaniami. Jest to jednak dobra wiadomość dla naukowca, gdyż P=NP to jeden z siedmiu matematycznych problemów milenijnych, a za rozwiązanie każdego z nich Clay Mathematic Institute wypłaci milion dolarów nagrody.
Hipoteza P≠NP to pytanie czy dla każdego zagadnienia, dla którego możliwa jest weryfikacja rozwiązania w czasie wielomianowym (dla zadanego problemu górną granicę czasu wykonywania danego algorytmu możemy matematycznie określić wielomianem pewnego określonego, ale stałego stopnia zależnym od danych wejściowych), możliwe jest również znalezienie tego rozwiązania w takim czasie?
W praktyce oznacza to, że jeśli np. postawimy przed komputerem zadanie faktoryzacji (rozkładu na czynniki) danej liczby, to niezwykle istotny jest czas, w jakim zadanie zostanie wykonane. Zbyt długi czas oznacza, że np. łamanie interesującego nas szyfru jest nieopłacalne gdyż użytkownik i tak go w międzyczasie zmieni, a próba dokładnego poznania funkcji skomplikowanej cząsteczki jest skazana na niepowodzenie, gdyż potrwa zbyt długo, musimy zatem zadowolić się pewnym przybliżeniem.
Czas potrzebny do wykonania zadania to P, a czas potrzebny do weryfikacji wyniku to NP. Jeśli zatem P=NP, oznacza to, że każdy problem, którego rozwiązanie może być szybko zweryfikowane, może zostać też szybko rozwiązany.
Deolalikar doszedł do wniosku, że P≠NP skupiając się na problemie spełnialności, czyli, jak czytamy w Wikipedii, pytaniu czy dla danej formuły logicznej istnieje takie podstawienie zmiennych zdaniowych, żeby formuła była prawdziwa. Problem spełnialności jest problemem NP.
Matematyk twierdzi, że udowodnił, iż problemu spełnialności nie można szybko rozwiązać w czasie wielomianowym, a zatem nie jest to problem P. Czyli P≠NP.
Pozytywna weryfikacja obliczeń Deolalikara będzie oznaczała, że klasy P i NP nie są identyczne, co z kolei wyznacza nieprzekraczalne granice dla komputerów pokazując, że pewne zadania są dla nich zbyt skomplikowane. Pocieszający jest fakt, że nie dla wszystkich zadań - należy do nich faktoryzacja - rozwiązanie Deolalikara oznacza nieprzekraczalną granicę. Jednak cała klasa zadań, zwanych problemami NP-zupełnymi, będzie nie do rozwiązania. Do NP-zupełnych należy słynny problem komiwojażera, czyli postawione przed wędrownym sprzedawcą zadanie znalezienia optymalnej trasy pomiędzy kilkoma punktami.
Komentarze (16)
Przemek Kobel, 11 sierpnia 2010, 17:22
To było wczoraj. Dzisiaj już wiadomo, że z dowodem jest kilka poważnych problemów, niemniej nadal jest uważnie studiowany, bo ponoć zawiera szereg bardzo ciekawych pomysłów.
Jarek Duda, 11 sierpnia 2010, 17:57
Jakoś sobie nie wyobrażam takiego dowodu ... musi uwzględniać wszelkie możliwe klasy algorytmów ... jak zamianę na ciągły problem ...
Na przykład w 3SAT pytaniem jest czy można tak zawartościować zmienne, żeby wszystkie zadane alternatywy trójek z negacjami (np. x lub (nie y) lub z) były spełnione.
No to potraktujmy zmienne jako liczby rzeczywiste - alternatywa (x lub y) jest spełniona wtw
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2) ma minimum (w 0)
żeby przetłumaczyć alternatywę trójek w ten sposób, potrzebujemy iloczyn 7 takich wyrazów (zamiast 3).
Teraz sumujemy takie wyrazy dla wszystkich alternatyw z 3SAT i przetłumaczyliśmy problem na optymalizację globalną (wielomianu stopnia 14):
optimum globalne jest 0 wtw odpowiedź na oryginalne pytanie jest tak
W tym momencie wchodzi ciągła analiza, metody gradientowe, wygładzanie lokalnych minimów, algorytmy genetyczne, różne sposób zamiany ...
http://en.wikipedia.org/wiki/Cooperative_optimization
Kombinatoryka używana w tego typu dowodach to zupełnie inny świat ...
Przemek Kobel, 11 sierpnia 2010, 19:08
W treści notki jest adres PDF-a z dzisiejszą wersją tego dokumentu. Poprzednią można oglądać online: http://www.scribd.com/doc/35539144/pnp12pt
Szczerze mówiąc, z perspektywy laika nie wyobrażam sobie przeglądania tego bez skończonej lektury przynajmniej Drogi do rzeczywistości...
Krzysztof-n, 11 sierpnia 2010, 19:25
Po przeczytaniu tytułu byłem przekonany, że chodzi tu o jakiś rodzaj tranzystora...
A tu zonk, to jest informacja do tak wąskiego grona odbiorców, że chyba nawet nie mam takiego znajomego ...
Alek, 11 sierpnia 2010, 21:13
Nie szkodzi, że do wąskiego grona. Ja też nie wszystko kumam w tej kwestii, ale coś tam przybliżyłem do zrozumienia
.
antoniossss, 11 sierpnia 2010, 22:35
mnie też zdawało się, że chodzi o jakiś bipolarek... ale później coś tam zaświtało w główce, że było to zagadnienie na wykładach a nawet później na egzaminie z algorytmów, na które odpowiedzią prawidłową (pyt o P=NP?) było "Nie wiem"
Alek, 11 sierpnia 2010, 23:22
Hm, może profesor po cichu liczył, że jakiś student rozwiąże tę kwestię na potrzeby egzaminu
ozeo, 11 sierpnia 2010, 23:55
Jeśli dowód jest prawdziwy i nie zawiera luk logicznych to jest hmm coś wielkiego w świecie informatyki.
Przypuszczalnie uprości to wiele innych dowodów w algorytmice. To jest jedna z tych rzeczy o których będą się studenci pierwszych lat kierunków technicznych uczyć w podręcznikach.
Tolo, 13 sierpnia 2010, 00:13
W sumie to jest to coś czego się można było intuicyjnie spodziewać (to znaczy ze P nie równa się NP) tylko nie było dowodu (oczywiście jeśli założymy prawdziwość tego). Natomiast dowód przeciwny (P=NP którego tez nie było i chyba już nie będzie
) mógł by trochę rzeczy wywrócić do góry nogami, dlatego przynajmniej dla mnie wydawał się bardziej prawdopodobny dowód pierwszy bo jakoś nic się specjalnie samo walić ani przewracać do góry nogami nie chciało. W sumie trochę szkoda bo mogło być wesoło 
rmaciej1983, 20 sierpnia 2010, 12:29
Do Dudy:
Widać, że nie znasz definicji algorytmu. Można uwzględnić KAŻDY możliwy algorytm łącznie z proponowaną przez Ciebie transformacją do problemu ciągłego, gdyż w informatyce teoretycznej rozważa się różne tak zwane modele obliczeń (np. maszynę Turinga bądź obwody logiczne), które są równoważne abstrakcyjnemu komputerowi.
Do Toto:
Ja tam w żaden sposób nie mogę domyślić się tego intuicyjnie. Analizując problem NP vs P raz byłem skłonny przypuszczać, że raczej P != NP, a raz, że P = NP.
Gdyby P = NP, to niby co przewróciłoby się do góry nogami?
megli, 3 października 2010, 16:43
Do autora artykułu:
Zdanie niepoprawne:
"Czas potrzebny do wykonania zadania to P, a czas potrzebny do weryfikacji wyniku to NP"
Prawdopodobnie autorowi chodziło o fakt, że dla problemu z klasy P można znaleźć rozwiązanie w czasie wielomianowym(czyli "szybko"), dla problemu z klasy NP weryfikacja poprawności znanego wyniku jest możliwa w czasie wielomianowym(czyli "szybko").
Problem spełnialności SAT jest problemem NP zupełnym, czyli każdy inny problem NP może być przekształcony do problemu SAT w czasie wielomianowym(a zatem jeśli potrafilibyśmy rozwiązać problem SAT w czasie wielomianowym, każdy inny problem NP też byśmy potrafili, wtedy mamy udowodnione, że P=NP)
Jeżeli Deolalikar udowodnił, że SAT nie może być rozwiązany w czasie wielomianowym, oznacza to że P!=NP
(nie jest możliwe rozwiązanie żadnego problemu NP w czasie wielomianowym, bo po przekształceniu do problemu SAT przeczyłoby to faktowi że SAT nie można rozwiązać w ten sposób - wielomianowo)
Do Dudy:
Pomijając to co napisał kolega wcześniej(o metodach informatyki teoretycznej), większość proponowanych tu podejść w ogóle nie gwarantuje znalezienia rozwiązania optymalnego(metody gradientowe, algorytmy genetyczne itd.)
Często metody te nie mają w ogóle określonego kryterium zakończenia obliczeń, np po pewnym czasie działania algorytmu genetycznego można go zatrzymać i przyjrzeć się wynikowi. Wiemy np że wynik jest lepszy od innych, które znaleźliśmy, ale nie wiemy czy jest to wynik optymalny.
Do rmaciej1983:
Na pytanie: "Gdyby P=NP, to niby co przewróciłoby się do góry nogami?"
Po samym udowodnieniu, że P=NP jeszcze nic. Oznaczałoby to natomiast, że istnieją efektywne(wielomianowe) algorytmy dla wszystkich problemów NP. Istnieją, czyli można je wymyślić, a zatem możemy np łamać szyfry w sensownym czasie. Cała współczesna kryptografia mogłaby upaść(np bankowość elektroniczna).
W szczególnośći rozwiązanie dowolnego problemu NPC(NP zupełnego)w czasie wielomianowym spowodowałoby, że znalibyśmy rozwiązania wszystkich problemów NP w czasie wielomianowym.
Informatyk
Jarek Duda, 3 października 2010, 18:16
Przepraszam, nie zauważyłem odpowiedzi ...
Owszem - transformacja którą proponuję (z tego co szukałem, wcześniejsze wymagały dodatkowo olbrzymiej ilości więzów
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.726&rep=rep1&type=pdf ), dalej jest algorytmem.
Dlatego pisałem 'klasa algorytmów' - bo mam wrażenie że dla większości informatyków tego typu problemy można atakować tylko kombinatorycznie - rozważając przestrzeń konkretnych zerojedynkowych wartościowań zmiennych - i tak wyglądały chyba wszelkie ataki na P!=NP jakie widziałem.
Transformacja na problem ciągły powoduje że zaczynamy pracować dosłownie pomiędzy tymi wartościowaniami - jasne, w praktyce mamy dostęp 'tylko' do przeliczalnej ilości z nich, jednak próby panowania na pokryciu tego zbioru pod atak na P!=NP wydają się być jakościowo znacznie trudniejsze niż przy dyskretnym obrazie (może nie są?) ... poza tym w porównaniu z dyskretnym, dochodzi przede wszystkim wyglądające bardzo potężne narzędzie jakim jest gradient ...
A co do "Gdyby P=NP, to niby co przewróciłoby się do góry nogami?" to na przykład mamy AKS od jakichś 8 lat ... a (mimo że test pierwszości jest podstawą RSA) z tego co wiem dalej nie opłaca się go używać ...
Szczerze to chyba jedyne co taki ewentualny dowód by zmienił to zawalenie systematyki informatyków ...
Natomiast z rozwiązywaniem niezwykle złożonych problemów doskonale radzi sobie fizyka ... i może pozwala na jeszcze inne 'nietypowe' sposoby jej wykorzystania niż komputery kwantowe, np. http://www.electro-tech-online.com/electronic-projects-design-ideas-reviews/86973-continious-time-loop-computer.html
megli, 3 października 2010, 19:57
Do Jarka Dudy:
Znane metody łamania RSA opierają się chyba na faktoryzacji, czyli rozkładzie liczb na czynniki pierwsze.
Nie jest znany algorytm wielomianowy do faktoryzacji.
Mimo wszystko, rozumiem co miałeś na myśli:
Chociaż mamy AKS, czyli wielomianowy algorytm testujący czy liczba jest pierwsza nie okazało się to żadną rewolucją, a nawet do testów pierwszości używa się innych algorytmów.
Czyli pewnie masz rację, że samo udowodnienie że P=NP nie było by od razu jakąś rewolucją. Może gdyby udało się:
1. Udowodnić, że P=NP
2. Znaleźć wielomianowy algorytm problemu NPC ograniczony wielomianem niewielkiego stopnia(bardzo wątpliwe)
3. Transformacje problemów NP do problemu NPC z 2 byłyby ograniczone wielomianem niewielkiego stopnia
to może rzeczywiście mielibyśmy poważne konsekwencje praktyczne.
Jarek Duda, 3 października 2010, 20:43
Przepraszam za znowu skrót myślowy - testy pierwszości są podstawą RSA w sensie generacji kluczy.
AKS w najlepszej implementacji ma ponoć złożoność 'długość liczby'^6, co przy kluczach 1024 bitowych staje się całkiem sporo.
Natomiast elementy tej słynnej rodziny problemów NP-zupełnych już same są powiązane transformacją wielomianową - czyli rozwiązywanie 3SAT w czasie wielomianowym, oznaczałoby że dla rozwiązywania jakichś praktycznych problemów mamy algorytm o złożoności będącej wielomianem znacznie wyższego stopnia.
W praktyce zwykle nie potrzebujemy takiego superoptymalnego rozwiązania (np. TSP) i algorytmy zachłanne czy probabilistyczne są zdecydowanie wystarczające.
'Cudownym' zastosowaniem o którym się mówi, to np. generacja dowodów twierdzeń - "znajdź ciąg implikacji, który prowadzi z aksjomatów do twierdzenia" - ale tu złożoność dalej będzie kosmiczna ... podobnie zresztą z łamaniem symetrycznych kryptosystemów - "znajdź klucz, którym dekodując, wynik ma korelacje" ... jeszcze rzeczywiście jest faktoryzacja, ale to trochę jednak inny, wydaje się że prostszy (np. Shor) problem - dlatego ogólnie uważam że używanie wszędzie RSA to kompletna nieodpowiedzialność, szczególnie że mamy dużo bardziej nieprzewidywalne - oparte na krzywych eliptycznych ...
Poza tym jest jeszcze wiele nieprzebadanych podejść w jakie można zaprzęgnąć fizykę (nie tylko QC i DNAcomp) i wcale bym się nie zdziwił, gdyby się okazało że pozwala ona nie tylko na wielomianowe, ale nawet praktyczne rozwiązywanie trudnych problemów ...
wilk, 4 października 2010, 00:09
Hmm, a algorytm Shora lub rho Pollarda?
megli, 5 października 2010, 14:43
Algorytm rho Pollarda jest probabilistyczny, daje tylko prawdopodobieństwo zwrócenia poprawnego wyniku. Jest wielomianowy, ale trzeba pamiętać, że daje wynik z określonym prawdopodobieństem.
Nic nie stoi na przeszkodzie, żeby go zmodyfikować tak aby prawdopodoieństwo było większe, ale kosztem czasu obliczeń.
W takim sensie istniały wielomianowe algorytmy do testowania pierwszości na długo przed AKS(i chyba nadal się ich używa)
Algorytm Shora jest kwantowy. Chociaż eksperymentalne komputery kwantowe już istnieją, są dosyć ograniczone(przynajmniej oficjalnie). Na chwilę obecną nie da się chyba zastosować algorytmu Shora w praktyce dla większych liczb(jak w kryptografii).
Stosowanie RSA pewnie ma wątpliwy sens jeżeli jest inaczej.
Może doprecyzuję to co napisałem wcześniej:
Nie jest znany deterministyczny wielomianowy algorytm faktoryzacji stosaowalny na klasycznych komputerach.
(Deterministyczny - zwracający zawsze poprawną odpowiedź)