Niektóre problemy matematyczne i logiczne da się szybko rozwiązać przy użyciu komputerów ? i stanowią one klasę problemów, z którą idealny komputer daje sobie radę w czasie będącym wielomianową funkcją zadanych mu parametrów (należą do tej klasy choćby układy równań liniowych czy problemy znajdowania najkrótszej drogi).
Niektóre problemy matematyczne i logiczne da się szybko rozwiązać przy użyciu komputerów ? i stanowią one klasę problemów, z którą idealny komputer daje sobie radę w czasie będącym wielomianową funkcją zadanych mu parametrów (należą do tej klasy choćby układy równań liniowych czy problemy znajdowania najkrótszej drogi). Istnieją jednak zagadnienia, których rozwiązania znamy, ale nie są to rozwiązania równie ?szybkie?, jak w wypadku poprzednim. Czy da się wszystkie podobne problemy (zgrupowane w pewnej klasie, oznaczonej jako NP) rozwiązać szybciej? Czy też istnieją takie, których analizy nie da się już przyspieszyć w żaden sposób? Pytanie ciekawe i szalenie istotne z praktycznego punktu widzenia, bowiem problemy te związane są z kryptografią (łamaniem kodów), kolorowaniem map czy układaniem harmonogramów.
Stephen Cook i Leonid Levin sformułowali problem P (tzn. łatwy do znalezienia) kontra NP (tzn. łatwy do sprawdzenia) niezależnie od siebie w 1971 roku.
Przykładem problemu NP jest tzw. problem komiwojażera. Jest to zagadnienie z teorii grafów, polegające na znalezieniu w nim minimalnego cyklu Hamiltona. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast. Należy znaleźć najkrótszą trasę wychodzącą z danego miasta, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do tego samego miasta.
Nie są znane algorytmy dające dokładne rozwiązanie tego problemu w czasie wielomianowym. W praktyce najefektywniejszymi sposobami jego rozwiązania są algorytmy genetyczne, często wykorzystywane w połączeniu z heurystycznymi (np. heurystyka najbliższego sąsiada). Są to jednak metody dające w większości jedynie rozwiązania bliskie optymalnemu. Niekiedy tylko zdarza się, że otrzymane rozwiązanie jest optymalne. Zależy to głównie od liczby punktów oraz czasem szczęścia (generacja populacji początkowej, krzyżowanie oraz mutacja w algorytmach genetycznych zawierają element losowy).
