Problema $SAT$ este $NP-completă$. Defapt, este prima problemă $NP-completă$ găsită. Stephen Cook a demonstrat $NP-completitudinea$ ei în 1971. Pe vremea aceea nu se ştia nici măcar că problemele $NP-complete$ există. Această problemă rămâne $NP-completă$ chiar dacă restricţionăm expresiile la unele care în forma normal conjunctivă au doar trei literali. Problema satisfiabilităţii pentru asemenea expresii se numeşte $3SAT$, şi multe probleme pot fi demonstrate a fi $NP-complete$ prin reducerea la această problemă. Din fericire, problema $2SAT$, adică cea pentru care în fiecare propoziţie există doar $2$ literali se poate rezolva eficient. Restul articolului va prezenta trei metode de rezolvare a problemei $2SAT$ şi câteva aplicaţii ale acesteia la concursuri de programare.
Un exemplu de problemă $2SAT$ ar fi satisfiabilitatea formulei <tex> (x_{1} \vee \sim x_{2}) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee x_{2}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. Această formulă este satisfăcută de valorile <tex> \langle x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 1 \rangle </tex>. Pentru a satisface întreaga expresie trebuie ca în fiecare propoziţie cel puţin unul din cei doi literali să aibă valoarea de adevăr $1$.

O primă metodă de rezolvare ar fi să încercăm toate cele $2^4^$ posibilităţi de atribuire posibilă, dar această metodă are ordinul de complexitate $O(M * 2^N^)$ şi este eficientă doar pentru instanţe mici ale problemei.
 
Următoarea soluţie pare trivială, dar găsirea acestui algoritm şi realizarea faptului că el rezolvă corect problema este mai grea decât impresia lăsată după citirea ei. Considerăm o propoziţie oarecare cu două variabile $p$ şi $q$, apoi una dintre ele, de exemplu $p$. Dacă literalul în care apare $p$ este negat atunci îi atribuim valoarea $1$. Pentru ca propoziţia respectivă să aibă $1$ valoarea de adevăr atunci valoarea lui $q$ este fixată. Fixând şi valoarea lui $q$, probabil şi alte propoziţii ce conţin literalul $q$ vor avea celălalt literal fixat. Propagăm astfel o serie de schimbări.