P ≠ NP. Czy rozwiązano kolejny problem milenijny?

Przez wielu uczonych jest uważany za najważniejszy otwarty problem teorii obliczeń, a nawet całej informatyki teoretycznej. Czy tzw. problem P = NP,  jeden ze słynnych problemów milenijnych, doczekał się rozwiązania?

Przez wielu uczonych jest uważany za najważniejszy otwarty problem teorii obliczeń, a nawet całej informatyki teoretycznej. Czy tzw. problem P = NP,  jeden ze słynnych problemów milenijnych, doczekał się rozwiązania?

Czym są problemy NP?

Czy zdarza Ci się, Czytelniku, narzekać na szybkość swojego komputera? Cóż, możesz wówczas pocieszyć się myślą, że skoro zgodnie z prawem Moore'a komputery stają się z roku na rok szybsze, to z pewnością Twój następny nabytek poradzi sobie znacznie szybciej z wszelkimi obliczeniami.

Istnieją jednak problemy obliczeniowe, w starciu z którymi prawo Moore'a stanowi marne pocieszenie. Należą do nich tzw. problemy NP. Są to problemy, których rozwiązanie można co prawda sprawdzić w rozsądnym czasie (w tzw. czasie wielomianowym), ale których być może nie da się w takim czasie rozwiązać.

Do zagadnień tego rodzaju należy wariant słynnego Problemu Komiwojażera. Mając przed sobą mapę kraju z zaznaczonymi na niej miastami, które chce odwiedzić, oraz dokładną liczbę kilometrów, jaką chce przebyć, komiwojażer ma zdecydować, czy to w ogóle możliwe (nie wolno mu zawracać na drodze między dwoma miastami).

Rzecz jasna - istnieją algorytmy zdolne rozwiązać ten problem. Wystarczy jednak nieco zwiększyć liczbę miast, aby czas potrzebny tym algorytmom na przeprowadzenie obliczeń wzrósł wysoko ponad granice czyjejkolwiek cierpliwości.

Trudne czy nietrudne?

Niektórzy uczeni mieli nadzieję, że taki stan rzeczy jest jedynie efektem naszej niewiedzy i że w rzeczywistości wszystkie problemy NP są również P, tzn. da się dla nich znaleźć algorytmy pozwalające je rozwiązywać w czasie wielomianowym. Jeśli jednak rację ma Vinay Deolalikar, matematyk pracujący w laboratoriach firmy HP, są to złudne nadzieje. Kilka dni temu udostępnił on swoją pracę zatytułowaną po prostu "P ≠ NP", w której zamieszcza propozycję dowodu słuszności negatywnej odpowiedzi na tę postawioną przed niemal 40 laty hipotezę.

Choć pomyślny dowód, że P = NP, miałby znacznie dalej idące konsekwencje (oto wszystkie problemy NP w zasadzie dają się łatwo rozwiązać, po prostu jeszcze nie znaleziono dobrego algorytmu), to jeśli rozumowanie Deolalikara okaże się poprawne, oznaczać będzie znaczący postęp w informatyce teoretycznej.

Milion dolarów za twoje myśli

Fakt ten będzie mieć również wymierne znaczenie dla samego uczonego z HP Labs. Problem P=NP znajduje się bowiem na liście siedmiu problemów milenijnych. Za rozwiązanie każdego z nich amerykański Instytut Matematyczny Claya oferuje okrągły milion dolarów. Do tej pory pole oddał dopiero jeden problem milenijny. Tzw. Hipotezę Poincarégo udowodnił w serii prac publikowanych w latach 2002-2003 rosyjski matematyk, Grigorij Perelman. Nie przyjął jednak przysługującej mu nagrody.

Źródło: New Scientist