satisfiabiliteitsprobleem

Het satisfiabiliteitsprobleem, vaak afgekort als SAT, is een beslissingsprobleem uit de theoretische informatica en logica. Gegeven een booleaanse formule F uit de propositionele logica, meestal in conjunctieve normaalvorm (CNF), is er een toewijzing van de variabelen die F waar maakt? Als zo, is F satisfiable; anders is F unsatisfiable.

SAT is de bekendste NP-complete probleem; dit werd aangetoond in de Cook–Levin-theorema (1971). Als SAT in polynomiale tijd kan worden opgelost, kunnen alle problemen in NP eveneens in polynomiale tijd worden opgelost.

Veel voorkomende varianten: 2-SAT, waarin elke clausule uit maximaal twee literals bestaat, is in lineaire tijd oplosbaar; k-SAT is NP-compleet voor elke k ≥ 3.

Moderne SAT-solveren zoals DPLL en CDCL zijn praktische algoritmes die backtracking, clause learning en heuristieken combineren. Daarnaast bestaan er lokale zoekmethoden zoals WalkSAT voor grote formules.

Toepassingen omvatten hardware- en softwareverificatie, formele redenering en automatisering, planning en kunstmatige intelligentie. SAT vormt ook de basis voor vele problemen in optimalisatie en redenering.