[ Pobierz całość w formacie PDF ]
.Rysunek 4.8 daje pewne wskazówki, jak szybko zwiększają się niektóre omawiane przez nas liczby, kiedy rośnie N.Trudniejsze problemy klasyfikuje się jako NP, od angielskiego określenia non-deterministic polynomial, jeśli ich rozwiązania nie można zweryfikować w czasie wielomianowym.23 Najbardziej stroma krzywa na rys.4.8 charakteryzuje wzrost w przypadku problemów NP.Zauważmy, że we wszystkich podanych przykładach skoncentrowaliśmy się tylko na czasie znalezienia rozwiązania; nie powiedzieliśmy nic o pojemności pamięci, potrzebnej do przechowania informacji wygenerowanej w trakcie obliczeń.Nawet najskromniejsze obliczenie (algorytm), którego wyniki rosną w tempie 2N, wraz ze wzrostem liczby kroków N, szybko będzie potrzebować całego widzialnego wszechświata, żeby zapisać tymczasową informację obliczeniową, nawet jeśli jeden bit informacji zapisze się na jednym protonie.A we wszechświecie jest tylko 1079 protonów.W praktyce bardzo trudno dowieść, że jakiś problem nie da się rozwiązać w wielomianowym czasie (przykłady, które podaliśmy, należą do bardzo prostych).Obecnie nie ma więcej niż około tysiąca problemów podejrzewanych o przynależność do klasy NP.Jednym z wielkich nierozwiązanych problemów współczesnej matematyki jest ustalenie, czy któryś z problemów NP nie okaże się problemem P - a więc czy nie da się znaleźć rozwiązania w wielomianowym czasie, jeśli do sprawdzenia, czy jest ono prawdziwe, wystarczy czas wielomianowy.Zaskakujące, że wszystkie znane problemy NP, okazują się bardzo podobne w swojej wewnętrznej trudności.W 1970 roku Stephen Cook, wówczas absolwent Uniwersytetu Kalifornijskiego w Berkeley, dokonał wielkiego odkrycia - wykazał mianowicie, że wszystkie problemy NP można powiązać z jednym i tym samym problemem logicznym, stosując ogólną procedurę transformacji, którą można przeprowadzić w czasie wielomianowym.24 Oznacza to, że jeśli ktokolwiek znajdzie sposób na szybkie rozwiązanie któregokolwiek z problemów NP, to będzie możliwe szybkie rozwiązanie wszystkich problemów NP.Niepodatność to kłopotliwy problem także w biologii molekularnej.Otóż każdy żywy organizm zawiera białka, utworzone z łańcuchów aminokwasów, przypominających sznury korali.Kiedy aminokwasy znajdują się we właściwym porządku, DNA dostarcza informacji określającej, w jaki sposób cząsteczka białka ma się zwinąć, tworząc skomplikowaną trójwymiarową strukturę.Proces ten nazywa się zwijaniem białek.Na rys.4.9 pokazano przykładową zwiniętą cząsteczkę.25Problem, który chcieliby rozwiązać biolodzy molekularni jest następujący: jeśli mamy dany linearny łańcuch aminokwasów, jaka będzie jego ostateczna trójwymiarowa konfiguracja, kiedy się zwinie? Niesamowite jest to, że łańcuchy zawierające kilka tysięcy aminokwasów zwijają się w swój ostateczny kształt w ciągu mniej więcej jednej sekundy.Uważa się, że ostateczny kształt cząsteczki białka to taki, który minimalizuje energię potrzebną do podtrzymania jego struktury.Kiedy jednak próbujemy zaprogramować komputer, żeby zwinął białko, okazuje się to niemożliwe.Jeśli w cząsteczce jest tylko 100 aminokwasów, zwinięcie jej zajęłoby komputerowi ponad 1027 lat! A problem, okazuje się, jest jeszcze głębszy - w 1993 roku matematyk Aviezri Fraenkel wykazał, że sformułowanie problemu zwijania białek jest typu NP, a więc równie niepoddające się rozwiązaniu jak problem komiwojażera.26 Inne badania, z wykorzystaniem programowanego rozumowania heurystycznego, rozszerzającego zasięg badań komputerowych, przeprowadził George Rosę i jego współpracownicy.27 Wprowadzili rozmaite proste zasady, by pomóc białku się zwinąć - podali komputerowi proste reguły chemiczne, dzięki czemu nie musiał on sprawdzać wszystkich możliwości.Za pomocą tej techniki można przewidzieć większą część struktury zwiniętego białka.Wydaje się, że albo proces doboru naturalnego promował systemy żywe zbudowane z białek, które szczególnie łatwo się zwijały, albo problem zwijania białek nie musiał być rozwiązany przez Naturę z doskonałą dokładnością.Wystarczyło więc powtarzać proces mniej więcej jednakowo.Białka, dla których niewielkie niedokładności okazały się śmiertelne, po prostu nie przetrwały.Inni badacze sugerują, że być może Natura przeprowadza swoje obliczenia w sposób równoległy, jak komputer „kwantowy”, a nie liniowo, jak my.28Niepodatność na rozwiązanie problemów, które łatwo postawić, jak na przykład znalezienie najmniejszych podzielników bardzo dużych liczb, jest obecnie tak wielka, że stanowią one bazę całej nowoczesnej sztuki szyfrowania.29 Aby złamać szyfr wystarczy tylko znaleźć dwie wielkie liczby pierwsze, które pomnożone przez siebie dadzą liczbę mającą powiedzmy sto cyfr.Rozwiązanie tego zadania wymaga tak długiego czasu pracy komputera, że dany szyfr jest praktycznie całkowicie bezpieczny.Największa jak dotąd liczba, którą rozłożono na dwa czynniki pierwsze, ma 167 cyfr.Jej podzielniki mają 80 i 86 cyfr.Znalezienie ich zajęło Samuelowi Wagstaffowi i jego kolegom z Uniwersytetu Indiany 100 tysięcy godzin czasu komputerowego.30 Wynik przedstawiono na rys.4.10.Przedstawione przykłady dają nam pewien pogląd na to, czym jest nie-podatność, kiedy do atakowania trudnych problemów korzystamy z pomocy komputerów (lub jakichś innych urządzeń liczących).Nieważne, jak zaawansowana staje się nasza technika komputerowa, gdyż stawiane zadania mogą być astronomicznie długie (jest to pewne niedopowiedzenie, gdyż w naszej galaktyce jest tylko około 1011 gwiazd i mniej więcej tyle samo galaktyk zawiera się w widzialnym Wszechświecie).Być może przyjdzie nam się zmierzyć z zadaniem przełamania kodu, który wszechświat użył, żeby zakodować informację.Być może prawa Natury przekształcają początkowy stan Wszechświata w skomplikowany stan przyszły w taki sposób, że nawet jeśli znamy zarówno te prawa, jak i to, co się zmienia, oraz stan obecny, nie potrafimy odwrócić procesu i wy-dedukować, jaki był stan początkowy, gdyż obliczenia są „niepodatne”.Problem ten zaczyna się jako niedociągnięcie ludzkiego umysłu.Doskonale zdajemy sobie sprawę, że istnieją obliczenia, których zasada jest prosta, ale które wymagają tak długiego czasu, iż w praktyce ich wykonanie jest niemożliwe dla „nieuzbrojonego” ludzkiego umysłu (spróbujmy spisać pierwsze dwa miliony liczby naturalnych, używając pióra i papieru).Rozwój komputerów niewiele zmienia.Nawet jeśli połączymy w sieć olbrzymią liczbę tych urządzeń, może się okazać, że pełne zrozumienie skomplikowanego zjawiska w wielu naturalnych sytuacjach zajmie więcej czasu, niż możemy poświęcić na ich analizowanie.Życie jest krótkie, a obliczenia czasem bardzo, bardzo długie.Duch pograniczaJednakże w górach nawet Nowogwinejczycy nie potrafię znaleźć dziko rosnącego pożywienia w ilości dostatecznej do przeżycia.[.] A zatem przed nadejściem epoki samolotów, które umożliwity dokonywanie zrzutów z powietrza, wszystkie ekspedycje nowogwinejskie, penetrujące głębiej niż na odległość siedmio-milowego marszu od wybrzeża [ [ Pobierz całość w formacie PDF ]