It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete.
S-a demonstrat de către Ladner că dacă P ≠ NP atunci există probleme în NP care nu sunt nici în P nici NP-complete.