Kumpi seuraavista ei ole algoritmi: RSA, NP tai yleinen lukukenttäsiivu? Kirjoita edellisen kysymyksen perusteella tekstiyhteys, joka sisältää vastauksen. Se voi olla 1 - 20 lausetta. - Mitä tarkoitat?
Kokonaislukujen faktorisointiongelma on tietyn kokonaislukujen alkulukujen faktorisointiongelma. Päätösongelman muotoiltu, se on ongelma päättää, onko syöttöllä tekijä pienempi kuin k. Mitään tehokasta kokonaislukujen faktorisointialgoritmia ei tunneta, ja tämä tosiasia muodostaa useiden nykyaikaisten salausjärjestelmien, kuten RSA-algoritmin, perustan. Kokonaislukujen tekijänoikeus on NP:ssä ja co-NP:ssä (ja jopa UP:ssä ja co-UP:ssä). Jos ongelma on NP-täydellinen, polynomiaaliajan hierarkia romahtaa ensimmäiselle tasolleen (eli NP on yhtä kuin co-NP). Parhaiten tunnettu algoritmi kokonaislukujen faktorisoinnissa on yleinen lukukenttäsiivitys, joka kestää aikaa O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) n-bittisen kokonaislukujen faktorisointiin. Kuitenkin tunnetuin kvanttialgoritmi tähän ongelmaan, Shorin algoritmi, toimii polynomiaajassa. Valitettavasti tämä tosiasia ei kerro paljoakaan siitä, missä ongelma on suhteessa ei-kvanttiseen monimutkaisuusluokkaan.