Wyobraźmy sobie, że mamy do odwiedzenia kilka miast rozrzuconych na dużym obszarze. Chcemy zaplanować podróż tak, by koszty były możliwie najmniejsze, zastanawiamy się zatem w jakim porządku należałoby odwiedzać poszczególne miasta (każde z nich chcemy odwiedzić tylko jeden raz). Czy takie zadanie jest łatwo rozwiązać?
Problem jest banalny dla dwóch, trzech, czterech czy pięciu miast do odwiedzenia - wystarczy przedstawić sytuację na grafie z wagami, którego wierzchołki są reprezentacjami poszczególnych miast, a wagi nad krawędziami określają ile kilometrów jest między jednym a drugim miastem. Okazuje się jednak, że ilość możliwych dróg wzrasta zdecydowanie szybciej niż ilość miast, gdy dodajemy do trasy kolejny cel podróży. A zatem metoda polegająca na wypisywaniu tras i liczeniu ich odległości przestaje być skuteczna gdy rozważa się dłuższe wycieczki.
Czy ten problem jest praktyczny? Zdecydowanie. Przed dokładnie tego typu zadaniem stoją w swej działalności firmy kurierskie, linie lotnicze, przedstawiciele władz lokalnych odpowiedzialni za zarządzanie komunikacją miejską, czy wreszcie - jak w początkowym przykładzie - osoba planująca wakacyjną wycieczkę (a być może młoda para wybierająca się w podróż poślubną).
Problem ten jest także przykładem obrazującym trudności stojące przed matematyką oraz ograniczoność możliwości obliczeniowych komputerów. Oto bowiem dla pięciu miast mamy \(24\) możliwe trasy do przeanalizowania, natomiast dla - przykładowo - trzynastu miast liczba tras wynosi aż \(3,1 \cdot10^9\). Zadania tego nie rozwiąże dziś żaden komputer w czasie krótszym niż wiek. A przecież \(13\) miast (lub \(13\) przystanków autobusowych w średnim mieście, jak ktoś woli) to niezbyt dużo.
Problemy tego typu - tzn. takie, których rozwiązania nie da się znaleźć w tzw. czasie wielomianowym - nazywamy NP (niedeterministycznie wielomianowymi, z ang. nondeterministic polynomial) - innymi słowy, złożoność takiego problemu rośnie szybciej niż dowolny wielomian.