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.




