Waarom is dit belangrijk?
Zo kunnen computers bepalen of een reeks eisen samen een werkbare oplossing toelaat, bijvoorbeeld bij het indelen van taken. In wetenschap en techniek gebruiken ontwerpers dit bij het maken van hardware en de controle van software. Studenten en ontwikkelaars merken dat een programma zo een schema kan afwijzen of goedkeuren, al kan de zoektocht bij grote vraagstukken zeer lang duren of een oplossing missen.
Zo werkt het in de praktijk
Het systeem Satplan zoekt in de kunstmatige intelligentie een stappenplan via vervulbaarheid. Tang en Lin gebruikten een SAT-solver, een rekenprogramma voor dit probleem, om de stelling van Arrow te bewijzen. Die stelling beperkt welke stemregels tegelijk kunnen gelden.
Onderzoekers vergelijken solvers in de International SAT Solver Competition. Teams meten daar welke solver welke formules oplost. De wedstrijd heeft ook een onderdeel voor solvers op meerdere processoren.
Veel solvers bouwen op het DPLL-algoritme, een systematische zoektocht, of op CDCL. CDCL staat voor conflict-driven clause learning en leert uit een conflict een nieuwe voorwaarde. Solvers zetten de formule vaak eerst om naar de conjunctieve normaalvorm, een vaste schrijfwijze van losse eisen.




