Znajdź zawartość

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.