Naar inhoud
BetaAI Begrippen

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

NP-moeilijkheid

Engels: NP-hardness · Ook wel: NP-hardness, NP-hard, NP-moeilijk

In het kort

NP-moeilijkheid is in de complexiteitstheorie de eigenschap dat een probleem minstens zo zwaar is als de zwaarste problemen in NP. Zo’n probleem verschilt van een gewone berekening, want elk vraagstuk uit NP is, met rekenwerk dat beheersbaar meegroeit, tot dit probleem te herleiden. Een eenvoudig voorbeeld is het subset-sumprobleem: nagaan of een groep getallen een deelverzameling heeft die precies een gekozen som oplevert.

Waarom is dit belangrijk?

Herkennen van NP-moeilijkheid laat zien dat een rekenvraag te zwaar is voor een exact antwoord, zodat een werkbare benadering volstaat. In de logistiek geldt dat voor het handelsreizigersprobleem: een korte route langs veel adressen vinden zonder elke mogelijkheid te testen. Op school en op het werk verklaart dit waarom een berekende route soms niet de beste is: een snelle benadering kan iets afwijken van de kortste weg.

Zo werkt het in de praktijk

In de bio-informatica komt NP-moeilijkheid voor bij DNA-samenstelling en genoomsvergelijking. Een overzicht in Algorithms beschrijft ook fylogenie: het reconstrueren van stambomen. Geparametriseerde algoritmen lossen zulke taken op zolang één eigenschap van de gegevens klein blijft.

Voor machineplanning blijkt een groot deel van de vraagstukken NP-moeilijk. Een onderzoeksartikel beschrijft open vragen over vaste-parameteralgoritmen, voor één machine en voor meerdere gelijke machines. Die aanpak zoekt een exact antwoord dat snel blijft als één gekozen maat klein is.

Ontwerpers van algoritmen koppelen NP-moeilijkheid aan benaderingsalgoritmen. Bij APX blijft de afwijking van het beste antwoord binnen een vaste factor, en een PTAS (een benaderingsschema) maakt die afwijking zo klein als nodig is, met meer rekentijd.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026