section_heading: Nepotpuni problemi u NP
paragraph_text: mini|250px|Dijagram klasa složenosti uz pretpostavku da vrijedi P ≠ NP. Postojanje problema izvan klasa i P i NP-potpun u ovom slučaju je postavio Ladner. Drugo otvoreno pitanje vezano za problem P<nowiki> = </nowiki>NP jest postoje li problemi koji su u NP, ali ne i u P, koji nisu NP-potpuni. Drugim riječima, problemi koji trebaju biti riješeni u nedeterminističkom polinomnom vremenu, ali ne mogu biti svedeni na polinomno vrijeme iz drugih nedeterminističkih vremenski polinomnih problema. Jedan takav problem, za koji se zna da je NP ali ne i da je NP-potpun, jest problem izomorfizma grafa - problem koji pokušava odlučiti jesu li dva grafa izomorfna (tj. dijele li ista svojstva, v. izomorfni graf). Pokazano je da ako vrijedi P<nowiki> ≠ </nowiki>NP, da takvi problemi postoje.