* {'Soluţii pentru 2-SAT':2-sat#solutii-2-sat}
** {'Soluţie $O(M * 2^N^)$':2-sat#solutie-1}
** {'Soluţie $O(N * M)$':2-sat#solutie-2}

** {'Soluţie $O(N^2^ * M)$':2-sat#solutie-3}

** {'Soluţie $O(N^2^)$':2-sat#solutie-3}

** {'Soluţie $O(M + N)$':2-sat#solutie-4}
* {'Aplicaţii':2-sat#aplicatii}
** {'Party (preONI 2003/2004)':2-sat#party}

Să vedem cum funcţionează algoritmul pentru expresia: <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>. Considerăm propoziţia <tex> (x_{1} \vee \sim x_{2}) </tex> şi <tex> \langle x_{2} = 1 \rangle </tex>. Astfel, vom obţine mai departe <tex> (x_{1} \vee 0) \wedge (\sim x_{1} \vee \sim x_{3}) \wedge (x_{1} \vee 1) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{1}) </tex>. În propoziţia <tex> (x_{1} \vee 0) </tex>, <tex> x_{1} </tex> trebuie să fie egal cu <tex> 1 </tex>. Acum, expresia devine: <tex> (0\ \vee \sim x_{3}) \wedge (x_{4} \vee \sim x_{3}) \wedge (x_{4} \vee 0) </tex>. Din propoziţia <tex> (0\ \vee \sim x_{3}) </tex> obţinem <tex> \langle x_{3} = 0 \rangle </tex>, iar din <tex> (x_{4} \vee 0) </tex> obţinem <tex> \langle x_{4} = 1 \rangle </tex>. Deci, atribuirea satisfiabilă este <tex> \langle x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 1 \rangle </tex>.

h3(#solutie-3). Soluţie $O(N^2^ * M)$

h3(#solutie-3). Soluţie $O(N^2^)$

O altă soluţie elegantă se bazează pe o metodă randomizată: