Waarom is dit belangrijk?
Zo kan beveiliging van gegevens steunen op vraagstukken die een tegenstander met beperkte rekenkracht niet kan oplossen. In de cryptografie, een tak van digitale beveiliging, gebeurt dat bij systemen zoals RSA, die steunen op het ontbinden van grote getallen. Voor gebruikers van die systemen blijven versleutelde berichten zo beschermd, zolang die ontbinding te zwaar blijft, al is die aanname nog niet bewezen.
Zo werkt het in de praktijk
Onderzoekers passen computationele complexiteitstheorie toe bij het plannen van werk op machines. Een artikel in het European Journal of Operational Research beschrijft roosterproblemen in productie, diensten en informatieverwerking. De Universiteit Osnabrück en het project Scheduling Zoo houden die resultaten bij.
Onderzoekers vragen of elk probleem dat snel te controleren is, ook snel op te lossen is. Het Clay Mathematics Institute noemt die vraag een van de Millennium Prize Problems. Cook en Levin formuleerden de vraag in 1971.
Algoritmeontwerpers koppelen een nieuw probleem via reductie aan een NP-volledig probleem. Zo’n probleem hoort bij de zwaarste groep binnen NP. Zij schrijven het nieuwe probleem in beheerst groeiende rekentijd om naar een bekend geval, zoals het vervulbaarheidsprobleem.




