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 nomitaj NP-intermediaj problemoj. La grafeo izomorfismo problemo, la diskreta logaritmo problemo kaj la entjera faktorigo problemo estas ekzemploj de problemoj kreditaj esti NP-intermediaj. Ili estas kelkaj el la tre malmultaj NP-problemoj ne konataj esti en P aŭ esti NP-kompleta. Demando: Kiel estas tiuj problemoj nomitaj?
NP-intermediaj problemoj