next up previous contents index
Next: Elektroencefalogram: historia pewnego sygnału Up: Złożoność obliczeniowa. Previous: Notacja   Spis tresci   Skorowidz

Problem komiwojażera

Czy istnieje droga przechodząca przez wszystkie z $ N$ zadanych miast, krótsza niż $ X$ km? Jedyny znany algorytmA.1polega na kompletnym przeglądzie przestrzeni rozwiązań; ponieważ ilość możliwych dróg rośnie z ilością miast jak $ N!$, złożoność problemu wynosi $ {\mathcal O}(N!)$. Jednak jeśli ,,zgadniemy'' sekwencję kolejnych miast, to możemy w czasie wielomianowymA.2udowodnić, że przebyta droga spełnia warunki zadania. Jednak nie znamy deterministycznego algorytmu znajdowania rozwiązania lub udowadniania, że nie istnieje. Stąd problemy o tych własnościach nazywamy ,,niedeterministycznie wielomianowymi'' -- nondeterministic polynomial, czyli NP. Do tej klasy należy łamanie szyfrów, stosowanych aktualnie do zabezpieczania transakcji z użyciem kart kredytowych w Internecie. Co ciekawsze, nie udowodniono dotychczas, ze rozwiązanie tych problemów w czasie wielomianowym nie istnieje.


Porównajmy dla przykładu, ile cyfr ma...
$ 100^5$ 11 cyfr
$ 2^{100}$ 31 cyfr
$ 100!$ 161 cyfr
$ 100^{100}$ 201 cyfr
...a ile jest cyfr w liczbach określających
liczbę protonów w znanym wszechświecie 126 cyfr
liczbę mikrosekund od Wielkiego Wybuchu 24 cyfry

Sugeruje to, że niektóre z problemów rozstrzygalnych, dla których możemy bez kłopotu ocenić maksymalną ilość kroków potrzebnych do znalezienia rozwiązania, w skali naszego Wszechświata mogą być mimo to uznane za nieobliczalne:

  OBLICZALNOŚĆ  
w teorii   w praktyce
nie problemy nierozstrzygalne (np. stopu) nie
tak problemy trudno rozwiązywalne (w czasie wykładniczym) nie
tak problemy łatwo rozwiązywalne (w czasie wielomianowym) tak

Zainteresowanym tą tematyką polecam książkę [8] ,,o istocie informatyki''.


next up previous contents index
Next: Elektroencefalogram: historia pewnego sygnału Up: Złożoność obliczeniowa. Previous: Notacja   Spis tresci   Skorowidz
Piotr J. Durka 2004-01-05