Hvilket af følgende er ikke en klassifikation for problemer: NP, co-NP eller RSA? Skriv et svar i sammenhæng med det foregående spørgsmål. Det kan være 1 - 20 sætninger. Kontekst:
Problemet med faktorisering af et helt tal er det beregningsmæssige problem med at bestemme primfaktorisering af et givet helt tal. Udtrykt som et beslutningsproblem, er det problemet med at beslutte, om input har en faktor mindre end k. Ingen effektiv algoritme er kendt, og dette faktum danner grundlaget for flere moderne kryptografiske systemer, såsom RSA-algoritmen. Problemet med faktorisering af hele tal er i NP og i co-NP (og endda i UP og co-UP). Hvis problemet er NP-komplet, vil det polynomiale tidshierarki kollapse til sit første niveau (dvs. NP vil være lig med co-NP). Den bedst kendte algoritme for heltal faktorisering er den generelle talfelt sigte, som tager tid O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) til at faktorisere en n-bit heltal. Men den bedst kendte kvantalgoritme for dette problem, Shors algoritme, kører i polynomial tid. Desværre siger dette faktum ikke meget om, hvor problemet ligger i forhold til ikke-kvantiske kompleksitetsklasser.