Wanne daga cikin wadannan ba shine rarrabuwa ga matsaloli ba: NP, co-NP, ko RSA? Bisa ga tambayar da ta gabata, ka rubuta mahallin da ke ɗauke da amsar. Zai iya zama jumla 1 - 20. Abubuwan da ke ciki:
Matsalar factorization na lamba ɗaya ita ce matsalar ƙididdigar ƙayyade ainihin factorization na lambar da aka bayar. An bayyana shi azaman matsalar yanke shawara, matsala ce ta yanke shawara ko shigarwar tana da kashi ƙasa da k. Babu wani ingantaccen ma'auni na ma'auni na ma'auni da aka sani, kuma wannan hujja ta zama tushen tsarin tsarin zamani na zamani, irin su algorithm na RSA. Matsalar factorization na lamba tana cikin NP kuma a cikin co-NP (har ma a cikin UP da co-UP). Idan matsalar ta kasance NP-cikakke, tsarin lokaci na polynomial zai rushe zuwa matakinsa na farko (watau, NP zai zama daidai da co-NP). Mafi sanannun algorithm don factorization na lamba shi ne babban filin filin lamba, wanda ke ɗaukar lokaci O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) don yin factor a cikin n-bit lamba. Koyaya, mafi kyawun sanannen algorithm na wannan matsalar, algorithm na Shor, yana gudana a cikin lokacin polynomial. Abin takaici, wannan gaskiyar ba ta faɗi da yawa game da inda matsalar ta ta'allaka da nau'ikan rikitarwa ba-nau'in ba.