Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Computationele complexiteitstheorie

Engels: Computational complexity theory · Ook wel: computational complexity theory, computational complexity

In het kort

Computationele complexiteitstheorie is een vakgebied dat rekenproblemen indeelt naar hoe moeilijk ze van nature zijn. Een rekenprobleem is een taak die een computer oplost door een algoritme uit te voeren, dus met vaste wiskundige stappen. Onderzoekers vergelijken die groepen met elkaar en zien zo welke taken een computer snel oplost en welke voor elk algoritme veel rekentijd of extra geheugen vragen.

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.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026