Weet je nog wat een NP-volledig probleem is? Hoe verschilt het van gewoon NP?

NP (niet-deterministische polynomiale tijd) is een klasse problemen waarvoor de oplossing in polynomiale tijd kan worden gecontroleerd. Dat wil zeggen, als je een kandidaat-antwoord hebt, kun je snel controleren of het correct is of niet.

NP-complete problemen vormen een subset van NP die tegelijkertijd de "meest moeilijke" in deze klasse zijn. Als iemand een polynomiale algoritme zou vinden om een willekeurig NP-compleet probleem op te lossen, dan zouden alle problemen in NP in polynomiale tijd kunnen worden opgelost.

Belangrijkste verschil:

• NP: problemen waarvan oplossingen snel kunnen worden gecontroleerd.
• NP-complete: problemen in NP waaraan elke andere NP-probleem kan worden gereduceerd (d.w.z., ze zijn de "meest complexe" in NP).

Voorbeeld: het probleem van de maximale clique in een graaf is NP-compleet, en het probleem om te controleren of een subset van elementen optelt tot een gegeven getal, behoort tot NP.