A következők közül melyik nem minősül problémáknak: NP, co-NP vagy RSA? Az előző kérdés alapján írj egy szövegkörnyezetet, amely tartalmazza a választ. Lehet 1 - 20 mondat. A szövegkörnyezet:
Az egész számok faktorizálásának problémája az adott egész szám elsődleges faktorizálásának számítástechnikai problémája. Döntésproblémaként kifejezve, ez a probléma annak eldöntése, hogy a bemenő tényező kisebb-e, mint k. Nem ismert hatékony egész szám-faktorizációs algoritmus, és ez a tény képezi számos modern kriptográfiai rendszer alapját, mint például az RSA algoritmus. Az egész számok faktorizálásának problémája NP-ben és co-NP-ben van (és még UP-ben és co-UP-ben is). Ha a probléma NP-teljes, a polinomiális idő hierarchiája az első szintjére süllyed (azaz NP egyenlő lesz a co-NP-vel). Az egész számok faktorizálásának legismertebb algoritmusa az általános számmező szitája, amely időbe telik O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) egy n-bites egész szám faktorizálásához. Azonban a legismertebb kvantum algoritmus erre a problémára, a Shor algoritmus, polinomiális időben fut. Sajnos ez a tény nem sokat mond arról, hogy hol van a probléma a nem kvantum komplexitási osztályokkal kapcsolatban.