11.08.2010 / Gadzetomania.pl
 

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

  • Facebook Polub
  • LinkedIn Opublikuj
  • Twitter Udostępnij
Tomasz Miller
 

Trzeba będzie zaktualizować t-shirt?

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

  • Facebook Polub
  • LinkedIn Opublikuj
  • Twitter Udostępnij
wizytówki firm
szukasz klientów dla firmy?
  • NuOrder NuOrder

    Jesteśmy partnerem marek w zakresie kompleksowych działań interaktywnych i kampanii performance. Budujemy...

    Zobacz profil w katalogu firm
  • grey tree sp. z o.o. grey tree sp. z o.o.

    Istniejemy na rynku reklamowym od 2007 r. Przez ten czas zbudowaliśmy nie tylko naszą markę, ale przede wszystkim...

    Zobacz profil w katalogu firm
  • TBMS Digital Marketing Agency TBMS Digital Marketing Agency

    Projektujemy i wdrażamy strony internetowe - m.in. sklepy, landing page, firmowe. Świadczymy usługi związane z...

    Zobacz profil w katalogu firm
Trwa zapisywanie komentarza
Dodaj komentarz
Zaloguj się
Jeśli nie masz jeszcze konta w Interaktywnie.com - możesz się zarejestrować albo
wymagane
 
obrazek nieczytelny
 
 
wyślij
wizytówki firm
szukasz klientów dla firmy?
NuOrder
 
Arrow
newsletter
Arrow
Loader
Up Down
ostatnie komentarze
 
Dołącz do społeczności interaktywnie.com
 
 
 
 
© 2019 interaktywnie.com. All rights reserved.