Wraz z definicjami klas problemów NP i NP-zupełnych ma to następujące konsekwencje: problem optymalizacyjny, którego wersja decyzyjna jest NP-zupełna, jest problemem NP-trudnym; NP-trudny problem jest co najmniej tak trudny, jak problem ponieważ jest problemem NP-zupełnym, toteż należy on do problemów najtrudniejszych w klasie NP, dlatego NP-trudny problem jest co najmniej tak trudny, jak cała klasa NP; ponieważ wszystkie problemy NP-zupełne transformują się wzajemnie do siebie (zwykłą) transformacją wielomianową (nie Turinga), to również wszystkie problemy NP-zupełne można rozwiązać przez redukcję do NP-trudnego problemu ponadto, jeśli to problemy NP-trudne nie mają rozwiązań w czasie wielomianowym, natomiast rozstrzygnięcie nie przesądza o wielomianowej rozwiązywalności wszystkich problemów NP-trudnych; jeżeli problem należy do klasy NP, to jest też problemem NP-zupełnym (gdyż wraz z istniejącą transformacją Turinga spełnia definicję problemu NP-zupełnego).
Przykłady problem komiwojażera problem plecakowy problem zbioru niezależnego problem zbioru wierzchołków rozrywających cykle
Zobacz też algorytm pseudowielomianowy problem liczbowy problem silnie NP-zupełny