Problema satisfiabilitatii, notata prescurtat cu SAT cere determinarea existentei unei atribuiri satisfiabile pentru o formula booleana. O atribuire de valori booleene pentru variabilele acestei expresii se numeste atribuire satisfiabila daca evaluarea expresiei dupa atribuirea valorilor da rezultat ca valoare de adevar $"adevarat"$. Un exemplu de formula ar fi:
$((x{~1~} SAU x{~2~}) SI ((NOT x{~3~}) SI x{~1~}) SAU x{~4~})$
aceasta avand o atribuire satisfiabila $x{~1~}=1 x{~2~}=0 x{~3~}=0 x{~4~}=1$.

Orice formula booleana poate fi transformata in 2 forme: forma normal conjunctiva (expresia este scrisa ca o conjunctie de propozitii $P{~1~} SI P{~2~} SI ... SI P{~n~}$  si forma normal disjunctiva.

h2. Date de intrare