Ambayo ya yafuatayo si uainishaji kwa ajili ya matatizo: NP, co-NP, au RSA? Kwa sababu ya swali lililotangulia, andika muktadha unaotoa jibu. Inaweza kuwa sentensi 1 - 20. Muktadha:
Factorization ya integer tatizo ni tatizo la kompyuta ya kuamua factorization msingi wa integer fulani. Imeelezwa kama tatizo la uamuzi, ni tatizo la kuamua kama pembejeo ina sababu chini ya k. Hakuna algorithm ya ufanisi ya hesabu kamili inayojulikana, na ukweli huu huunda msingi wa mifumo kadhaa ya kisasa ya cryptographic, kama vile algorithm ya RSA. Tatizo factorization integer ni katika NP na katika co-NP (na hata katika UP na co-UP). Kama tatizo ni NP-kamili, polynomial wakati uongozi kuanguka kwa ngazi yake ya kwanza (yaani, NP itakuwa sawa na co-NP). Algorithm inayojulikana zaidi kwa integer factorization ni jumla ya idadi ya uwanja mchanganuo, ambayo inachukua muda O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) kwa sababu ya integer n-bit. Hata hivyo, quantum algorithm inayojulikana zaidi kwa tatizo hili, algorithm ya Shor, inafanya kazi katika muda wa polynomial. Kwa bahati mbaya, ukweli huu haisemi mengi kuhusu ambapo tatizo liko kuhusiana na madarasa yasiyo ya quantum utata.