Klasa NP obejmuje wszystkie matematyczne problemy rozwiazywalne w czasie wielomianowym na TM (maszynie Turinga) typu niedeterministycznego. Oznacza to, ze jezeli maszyna zgadnie rozwiazanie, to jest w stanie zweryfikowac jego poprawnosc w czasie wielomianowym. Nie jest to oczywiscie faktyczne rozwiazanie problemu, poniewaz nie ma zadnej pewnosci, ze maszyna odgadnie poprawne rozwiazanie.

W rzeczywistosci systematyczne (deterministyczne) rozwiazanie problemu klasy NP wymaga czasu wykladniczego. Przykladem takiego problemu jest wlasnie zagadnienie plecakowe.