Naar inhoud
BetaAI Begrippen

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

NP-volledigheid

Engels: NP-completeness · Ook wel: NP-completeness, NP-complete

In het kort

NP-volledigheid is een eigenschap van bepaalde ja-nee-problemen in de complexiteitstheorie, de studie van rekentijd. Een voorgestelde oplossing is snel te controleren en het zoeken verloopt via grof zoekwerk, terwijl dit probleem elk ander probleem van dat type kan nabootsen. Het antwoord is ja bij minstens één geldige oplossing en nee zonder zo'n oplossing, en een snelle methode voor één NP-volledig probleem, zoals het knapzakprobleem, levert daarmee ook een snelle methode voor alle andere op.

Waarom is dit belangrijk?

Door NP-volledigheid kunnen onderzoekers herkennen welke planningsvragen te groot zijn voor een exacte berekening in redelijke tijd. In de logistiek gebruiken planners die kennis voor roosters en het indelen van ritten, en zoeken ze een bruikbare benadering. Voor werknemers en planners betekent dat een rooster dat op tijd klaar is, maar niet altijd de beste verdeling van taken en ritten geeft.

Zo werkt het in de praktijk

Onderzoekers, onder meer aan Princeton University, zetten SAT-heuristieken in bij AI-planning, het testen van schakelingen en het controleren van software. SAT geldt daarbij als het standaardvoorbeeld van een NP-volledig probleem.

Het Clay Mathematics Institute rekende de vraag of P gelijk is aan NP tot de Millennium Prize Problems. In de complexiteitstheorie zoeken onderzoekers een bewijs voor of tegen die gelijkheid.

Informatici pakken NP-volledige problemen aan met heuristieken en benaderingsalgoritmen. Een benaderingsalgoritme levert een oplossing met een bewezen afstand tot het beste antwoord. Een heuristiek, zoals simulated annealing, zoekt een bruikbare uitkomst zonder die vaste garantie.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026