Rigardu la malsupran trairejon kaj poste respondu la demandon poste en la sama lingvo kiel la trairejo:  Trairejo: Estis montrite de Ladner ke se P ≠ NP tiam ekzistas problemoj en NP kiuj estas nek en P nek NP-kompleta. Tiaj problemoj estas nomataj NP-intermediaj problemoj. La grafeo izomorfismo problemo, la diskreta logaritmo problemo kaj la entjera faktorigo problemo estas ekzemploj de problemoj kreditaj esti NP-intermediate. Ili estas kelkaj el la tre malmultaj NP-problemoj ne konataj esti en P aŭ esti NP-kompletaj.  Demando: Kiel nomiĝas tiuj problemoj?
NP-intermediaj problemoj