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? Czy zdarza Ci się, Czytelniku, narzekać na szybkość swojego komputera? Cóż, możesz wówczas pocieszać się myślą, że skoro zgodnie z prawem Moore’a komputery stają się z [...]

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?

Czy zdarza Ci się, Czytelniku, narzekać na szybkość swojego komputera? Cóż, możesz wówczas pocieszać 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.

Niektórzy uczeni mieli nadzieję, że taki stan rzeczy jest jedynie efektem naszej niewiedzy. Ż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 swoją 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 (wiele trudnych problemów, w tym kryptograficznych, po prostu czeka na dostatecznie błyskotliwego algorytmika), to jeśli rozumowanie Deolalikara okaże się poprawne, oznaczać będzie znaczący postęp w informatyce teoretycznej.

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.

Przypomnijmy, że 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: gadzetomania.pl

Pobierz ebook "Social media marketing dla firm i agencje się w nim specjalizujące"