Problemy NP-pośrednie Jeżeli P ≠ NP, nie wszystkie problemy z NP muszą być NP-zupełne. Twierdzenie Ladnera pokazuje, że przy tym założeniu istnieją problemy pośrednie: należące do NP, ale nienależące ani do P, ani do klasy problemów NP-zupełnych. Jako kandydatów na takie problemy często wskazuje się m.in. oraz decyzyjne wersje logarytmu dyskretnego i rozkładu liczby całkowitej na czynniki, choć ich dokładne miejsce w klasycznej hierarchii złożoności pozostaje otwarte.
Dla izomorfizmu grafów znane są dodatkowe przesłanki strukturalne: gdyby problem ten był NP-zupełny, hierarchia wielomianowa zapadłaby się do drugiego poziomu, co uważa się za mało prawdopodobne. Znane algorytmy dla tego problemu nie dają jednak klasycznego algorytmu wielomianowego. Istotnym postępem był quasi-wielomianowy algorytm László Babaiego.
Decyzyjną wersję faktoryzacji można ująć jako pytanie, czy dla danych liczb naturalnych i istnieje dzielnik liczby taki, że Problem ten należy do NP i co-NP, a nawet do klas UP i co-UP. Gdyby był NP-zupełny, hierarchia wielomianowa zapadłaby się do pierwszego poziomu. Z drugiej strony najlepsze klasyczne algorytmy faktoryzacji nie są wielomianowe, a algorytm Shora pokazuje wielomianową faktoryzację dopiero w modelu obliczeń kwantowych.