Sformułowanie Klasa P obejmuje problemy decyzyjne, które można rozwiązać na deterministycznym modelu obliczeń w czasie wielomianowym. Formalnie są to języki akceptowane przez deterministyczną maszynę Turinga w liczbie kroków ograniczonej wielomianem od długości wejścia. Klasa NP obejmuje problemy decyzyjne, dla których odpowiedź „tak” można zweryfikować w czasie wielomianowym, jeżeli podany jest odpowiedni certyfikat rozwiązania. Definicja przez certyfikaty jest równoważna standardowej definicji przez niedeterministyczną maszynę Turinga działającą w czasie wielomianowym. Każdy problem z P należy do NP, ponieważ algorytm rozwiązujący pozwala też szybko zweryfikować odpowiedź.
Pytanie P versus NP dotyczy tego, czy zachodzi również inkluzja odwrotna, czyli czy P = NP. Jeżeli P = NP, każdy problem z szybko weryfikowalnym rozwiązaniem miałby także algorytm znajdujący rozwiązanie w czasie wielomianowym. Jeżeli P ≠ NP, istnieją problemy, których rozwiązania da się szybko sprawdzać, ale których nie da się rozwiązywać w czasie wielomianowym.