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.




