mały|prawo|300px|Diagram Eulera dla problemów P, NP, NP-zupełnych i NP-trudnych. Istnienie problemów wewnątrz NP, ale nie należących ani do P, ani do NP-zupełnych, przy założeniu, że P≠NP, zostało udowodnione przez LadneraR.E. Ladner, On the structure of polynomial time reducibility, J.ACM, 22, 1975, s. 151–171. Corollary 1.1. ACM site..
Problem NP (, niedeterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.
Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność.
Przykładowy problem: Czy jakikolwiek niepusty podzbiór zadanego zbioru (np. ) sumuje się do zera?