Ladner näitas, et kui P ≠ NP, siis on NP-s probleeme, mis ei ole ei P ega NP-täielik. Selliseid probleeme nimetatakse NP-keskmised probleemideks. Graafi isomorfismide probleem, diskreetne logaritmide probleem ja täisarvude faktoriseerimise probleem on näited probleemidest, mis arvatakse olevat NP-keskmised. Need on mõned väga vähesed NP-probleemid, mida ei ole teada, et need on P-s või NP-täielik. Küsimus: Kuidas neid probleeme nimetatakse?
NP-vahepealsed probleemid