Problem komiwojażera

Czy istnieje droga przechodząca przez wszystkie z $N$ zadanych miast, krótsza niż $X$ km? Jedyny znany algorytm^A.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 wielomianowym^A.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''.