Hver af eftirfarandi er ekki eftirnafn einhvers: Shor eða RSA? Skrifaðu svarið í samhengi við fyrri spurningu. Það geta verið 1 - 20 setningar. Umfjöllun:
Málefni með hlutfallssetningu er tölfræðilegt vandamál við að ákvarða frumhlutfallssetningu fyrir ákveðna heildarfjölda. Það er vandamál að ákveða hvort innflutningurinn hafi hlutfall minni en k. Engin skilvirk altaliðgerðaralgorítmi er þekktur og þessi staðreynd er grundvöllur nokkurra nútíma dulritunarkerfa, svo sem RSA-algorítmsins. Málið með hlutfallssetningu er í NP og í co-NP (og jafnvel í UP og co-UP). Ef vandamálið er NP-fullkomið, mun fjölnafnartími hierarchy hrynja til fyrsta stigi (þ.e., NP verður jafnt co-NP). Besta þekkta reikniformin fyrir hlutfallssetningu er almenn númerfeldssífa, sem tekur tíma O(e(64/9) 1/3(n.log 2) 1/3(log (n.log 2)) 2/3) til að hlutfalda n-bit heiltal. Hins vegar, best þekktur quantum algoritmi fyrir þetta vandamál, Shor's algoritmi, virkar í polynomial tíma. Því miður segir þessi staðreynd ekki mikið um hvar vandamálið liggur í tengslum við ekki-kvantum flókið flokka.