Ladner viste, at hvis P ≠ NP, så findes der problemer i NP, der hverken er i P eller NP-komplet. Sådanne problemer kaldes NP-mellemliggende problemer. Graf isomorfismeproblemet, det diskrete logaritmeproblem og det heltal faktorisering problem er eksempler på problemer, der menes at være NP-mellemliggende. De er nogle af de meget få NP problemer, der ikke er kendt for at være i P eller at være NP-komplet. Spørgsmål: Hvad kaldes disse problemer?
NP-mellemliggende problemer