Czy istnieją problemy nie do rozwiązania?
Wiele lat temu spędziłem rok w laboratorium w Genewie w Szwajcarii. Pragnąc poprawić swój francuski, umówiłem się ze szwajcarskim inżynierem elektrykiem na ćwiczenia z „języka zawodowego”. Każdego dnia spotykaliśmy się na lunchu i przez czterdzieści pięć minut rozmawialiśmy po angielsku. Następnie udawaliśmy się do innego pokoju na kawę i trzy kwadranse francuskiego. Pewnego popołudnia mój przyjaciel powiedział coś, czego nie zapomnę: „Cały kłopot z tobą, Jim – kłopot ze wszystkimi Amerykanami – polega na tym, że uważacie, iż każdy problem można rozwiązać”.
Przez lata, gdy wraz z wiekiem nabierałem doświadczenia, zaczynałem godzić się z myślą, że niektóre problemy socjalne i polityczne, jeśli nie są nie do rozwiązania, to są tak temu bliskie, że niczym się to nie różni. Nadal skóra mi cierpnie ze strachu na myśl, że mogą istnieć problemy fizyczne lub matematyczne tego rodzaju.
Obecnie pod szyldem problemów nierozwiązywalnych możemy rozpatrywać dwa rodzaje zagadnień. Jedno dotyczy podstaw logicznych samej matematyki, drugie – współczesnych metod obliczeniowych. W końcu ubiegłego wieku wśród matematyków toczyła się poważna dyskusja na temat tego, czy zawsze możliwe jest określenie prawdziwości twierdzeń matematycznych. Bertrand Russell odkrył w 1901 roku paradoks, który podawał tę możliwość w wątpliwość (oto prosty przykład paradoksu Russella: w pewnym mieście fryzjer mówi, że będzie strzygł tych ludzi, którzy sami nie mogą się ostrzyc; czy ostrzyże on sam siebie?). Później, w 1931 roku, matematyk austriacki Kurt Godel udowodnił twierdzenie (nazywane teraz jego nazwiskiem) mówiące, że każdy dostatecznie skomplikowany system matematyczny zawiera twierdzenia, które są z pewnością prawdziwe, lecz których w ramach tego systemu nie da się udowodnić.
Jednakże w erze komputerów dyskusja nie koncentruje się już na kwestii, czy problem w zasadzie da się rozwiązać, lecz na tym, jak dużo czasu zajmie komputerowi rozwiązanie go. Okazuje się, że wśród problemów mamy do czynienia z hierarchią złożoności, opierającą się na ustaleniu, jak szybko wraz ze wzrostem ilościowym problemu rośnie czas obliczeń, przy założeniu, że komputer wyposażony jest w najbardziej wydajny zbiór instrukcji potrzebnych do jego rozwiązania.
Załóżmy na przykład, że do komputera, który ma poinformować nas o zaludnieniu pewnego obszaru, wprowadzamy dane dotyczące spisu ludności. Załóżmy również, że gdy dostarczymy informacji o jednym budynku w mieście, udzielenie informacji zajmie komputerowi jedną milisekundę. Możemy się więc spodziewać, że jeśli wprowadzimy dane o dwóch budynkach, udzielenie informacji zajmie nie więcej niż dwie milisekundy, dla dziesięciu budynków – poniżej dziesięciu milisekund i tak dalej (dobremu programowi zajęłoby to w rzeczywistości o wiele mniej czasu). Taki problem nazywany jest „praktycznie rozwiązywalnym” lub „klasy P złożoności”, ponieważ czas potrzebny na rozwiązanie rozbudowanego problemu zwiększa się (w tym przypadku) liniowo – podwojenie danych wejściowych co najwyżej podwaja czas wymagany na rozwiązanie. W rzeczywistości problem uważany jest za rozwiązywalny nawet wtedy, gdy czas ten rośnie do kwadratu, sześcianu lub innej potęgi (to znaczy, jeżeli rozważanie dwóch budynków w mieście zwiększa czas poczwórnie, trzech budynków – dziewięciokrotnie, i tak dalej). Wyrażenia matematyczne, w skład których wchodzą potęgi tego rodzaju, zwane są wielomianami, co wyjaśnia „P” w nazwie kategorii problemu (wielomian – ang. polynominal).
Problem, który nie może być rozwiązany w czasie opisywanym wielomianem, nazywany jest „praktycznie nierozwiązywalnym”.
Następny stopień w hierarchii złożoności stanowi kategoria problemów NP (niewielomianowych – ang. non-polynominal). Przykładem jest tu problem, w którym od komputera wymaga się ułożenia marszruty dla komiwojażera, pozwalającej odwiedzić każde z planowanych miast raz i tylko raz. Oczywiście, im więcej miast do odwiedzenia, tym więcej czasu zajmie komputerowi rozwiązanie problemu (nie oznacza to, że konkretny przykład problemu komiwojażera nie może być rozwiązany przez komputer – dla każdej określonej liczby miast problem może zostać rozwiązany, jeżeli tylko poczekamy wystarczająco długo). Problemy klasy NP mają tę charakterystyczną cechę, że jeżeli zgadniemy rozwiązanie, to możemy je zweryfikować w czasie wielomianowym, lecz nikt nie wie, czy najlepszy z możliwych zbiór instrukcji komputerowych będzie przebiegał w tym przedziale czasowym.
Obraz ten jest dodatkowo skomplikowany faktem, że wiele problemów typu NP jest sobie równoważnych – to znaczy, jeśli znamy rozwiązanie jednego, to po pewnych prostych przekształceniach otrzymamy rozwiązanie innego. Istnieje nawet zbiór problemów NP (zwanych „NP zupełnymi”), co do których można udowodnić, że stanowią najgorszy scenariusz dotyczący złożoności. Jeżeli któryś z nich jest praktycznie rozwiązywalny, wówczas wszystkie inne problemy NP też są. Podobnie, jeżeli (jak spodziewa się większość matematyków) jakiś NP-zupełny problem jest praktycznie nierozwiązywalny, wówczas żaden z nich nie ma rozwiązań. Zadaniem na dzisiaj dla teorii rozwiązywalności jest próba zrozumienia, w jaki sposób rozwiązywać problemy klasy NP.
Ta dyskusja o rozwiązywalności nie jest jedynie teoretyczna. W wielu wypadkach inżynierowie, aby lepiej projektować, muszą spoglądać na problem coraz bardziej szczegółowo, co jest analogiczne do zwiększania liczby miast w problemie komiwojażera. Wiedza o tym, że program komputerowy nie będzie musiał działać nieskończenie długo, jest zarówno rozstrzygająca, jak i praktyczna.