SAT fragt, ob eine aussagenlogische Formel eine erfüllende Belegung besitzt.
SAT war das erste als NP-vollständig bewiesene Problem (Satz von Cook-Levin).