Problemy NP-zupełne są jednocześnie w NP (rozwiązanie da się zweryfikować w czasie wielomianowym) i są NP-trudne. NP-trudne oznacza “co najmniej tak trudne jak problemy z NP”, ale nie musi należeć do NP (np. wersje optymalizacyjne). Jeśli jakikolwiek problem NP-zupełny ma algorytm wielomianowy, to P = NP.