NP-zupełność i NP-trudność W badaniu problemu P versus NP kluczową rolę odgrywają problemy NP-zupełne. Są to problemy należące do NP, do których każdy problem z NP można sprowadzić za pomocą redukcji wielomianowej. W typowym ujęciu taka redukcja jest funkcją obliczalną w czasie wielomianowym, która przekształca instancje jednego problemu w instancje drugiego, zachowując odpowiedź „tak” albo „nie”. Oznacza to, że szybki algorytm dla dowolnego problemu NP-zupełnego dawałby szybkie algorytmy dla wszystkich problemów z NP. W konsekwencji wykazanie, że choć jeden problem NP-zupełny należy do P, dowiodłoby równości P = NP.
Pojęciem szerszym jest NP-trudność. Problem NP-trudny to taki, do którego można zredukować każdy problem z NP. Nie musi on jednak sam należeć do NP ani nawet być problemem decyzyjnym. Problem NP-zupełny jest więc jednocześnie NP-trudny i należy do NP.
Z równością P = NP wiąże się też pytanie o zapadanie się szerszych klas złożoności. Gdyby P było równe NP, równe byłyby także NP i co-NP, a zapadłaby się do P. Większość badaczy uważa to za mało prawdopodobne, co jest jednym z powodów ostrożnego traktowania hipotezy P = NP.