Das Erfüllbarkeitsproblem der Aussagenlogik (SAT) ist eine Aufgabe aus dem Bereich der theoretischen Informatik. Es besteht darin, zu entscheiden, ob es für eine gegebene aussagenlogische Formel eine Belegung der Variablen gibt, so dass die Formel wahr wird.