Waarom is dit belangrijk?
Met NP kunnen onderzoekers rekenvragen indelen en de zwaarste groep aanwijzen, zodat duidelijk wordt waar een algemene snelle methode nog niet bekend is. In de logistiek horen routeplanning en het verdelen van lading daarbij, via het handelsreizigersprobleem en het knapzakprobleem. Voor planners en studenten blijft daardoor onzeker of zulke vragen altijd snel exact oplosbaar zijn, omdat nog niet vaststaat dat elke vraag in NP ook snel te berekenen is.
Zo werkt het in de praktijk
Ontwerpers van elektronica gebruiken problemen uit NP bij het controleren van chips. Een oplosser zoekt of een logische formule waar kan worden. Zo vergelijken zij twee ontwerpen en leggen zij paden op een programmeerbare chip.
Onderzoekers willen weten waarom zulke oplossers veel praktijkgevallen aankunnen. Willekeurige formules en formules uit de cryptografie blijven vaak lastig. Vijay Ganesh en Moshe Vardi zien de oplosser als een systeem dat een bewijs opbouwt.
Een veelgebruikte werkwijze is conflict-driven clause learning, kort CDCL. De oplosser haalt uit een tegenstrijdigheid een nieuwe regel en zoekt daarmee verder. Ontwikkelaars vergelijken zulke oplossers in SAT-wedstrijden.




