Kuris iš toliau išvardytų nėra problemų klasifikacija: NP, co-NP ar RSA? Atsižvelgiant į ankstesnį klausimą, parašykite kontekstą, kuriame būtų atsakymas. Tai gali būti nuo 1 iki 20 sakinių. Kontekstas:
Visų skaičių faktorizacijos problema yra skaičiavimo problema, kuria nustatoma tam tikro sveiko skaičiaus pirminė faktorizacija. Kaip sprendimo problema, tai yra problema, sprendžiant, ar įvesties koeficientas yra mažesnis nei k. Nėra žinomas veiksmingas sveiko skaičiaus faktorizuojimo algoritmas, ir šis faktas sudaro kelių šiuolaikinių kriptografijos sistemų, tokių kaip RSA algoritmas, pagrindą. Visų skaičių faktorizuoti problema yra NP ir co-NP (ir net UP ir co-UP). Jei problema yra NP-pilna, polinominės laiko hierarchija sumažės iki pirmojo lygio (t. y. NP bus lygus co-NP). Geriausias žinomas algoritmas yra bendrasis skaičiaus lauko sietas, kuriam reikia laiko O{\displaystyle O{\text{e}}} 64/9) 1/3{\text{n}}} n.log 2) 1/3{\text{n}}} log (n.log 2)) 2/3 {\\text{n}}} n-bitinio sveikojo skaičiaus suskaičiuoti. Tačiau geriausiai žinomas kvantinis algoritmas šiai problemai, Šoro algoritmas, veikia polinominiu laiku. Deja, šis faktas nedaug pasako apie tai, kur yra problema, susijusi su nekvantinėmis sudėtingumo klasėmis.