* {'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^)$':2-sat#solutie-3}

** {'Soluţie $O(N^2^ * M)$':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}

Următoarea soluţie pare trivială, dar găsirea acestui algoritm şi realizarea faptului că el rezolvă corect problema sunt mai grele 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$. Îi atribuim literalului în care apare $p$ valoarea $0$. Pentru ca propoziţia respectivă să aibă $1$ valoarea de adevăr, atunci valoarea lui $q$ trebuie 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. După ce toate schimbările forţate au fost făcute, propoziţiile rezultate vor fi de următoarele tipuri: <tex> a \vee b </tex>, <tex> 1 \vee 0 </tex>, <tex> 1 \vee 1 </tex>, <tex> 1 \vee b </tex>. Propoziţii de tip <tex> 0 \vee b </tex> nu pot apărea pentru că toate schimbările forţate au fost deja propagate. Dacă apare o propoziţie <tex> 0 \vee 0 </tex> atunci alegerea făcută pentru valoarea lui $p$ este greşită. Vom încerca şi alegerea opusă pentru $p$. Dacă ambele duc la o propoziţie de tip <tex> 0 \vee 0 </tex> atunci expresia nu poate fi satisfăcută. Propoziţiile de forma <tex> 1 \vee 0 </tex>, <tex> 1 \vee 1 </tex>, <tex> 1 \vee b </tex> pot fi ignorate. În acest fel am eliminat cel puţin o variabilă şi o propoziţie din expresie. Dacă expresia iniţială era satisfiabilă, atunci şi expresia din care s-au eliminat câteva propoziţii a rămas satisfiabilă. Continuând pe această idee obţinem un algoritm de complexitate $O(N * M)$, pentru că la fiecare atribuire de valoare pentru o variabilă parcurgem şirul de propoziţii o dată.

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>.

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} = 1, x_{3} = 0, x_{4} = 1 \rangle </tex>.

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

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

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

h3(#solutie-4). Soluţie $O(M + N)$

O a treia soluţie se bazează pe relaţia de implicaţie. Relaţia <tex> \rightarrow </tex> are următoarea tabelă de adevăr:

O a treia soluţie se bazează pe relaţia de implicaţie. Aceasta are următoarea tabelă de adevăr:

table{width: 90px; text-align: center}. | <tex> A </tex> | <tex> B </tex> | <tex> A \rightarrow B </tex> |
| <tex> 0 </tex> | <tex> 0 </tex> | <tex> 1 </tex>  |

| <tex> 1 </tex> | <tex> 0 </tex> | <tex> 0 </tex> |
| <tex> 1 </tex> | <tex> 1 </tex> | <tex> 1 </tex> |

Fiecare clauză <tex> A \vee B </tex> poate fi scrisă ca două implicaţii <tex> \sim A \rightarrow B </tex> şi <tex> \sim B \rightarrow A </tex>. Realizăm un graf al implicaţiilor. Astfel, nodurile grafului vor fi variabilele <tex> A </tex>, <tex> B </tex> <tex> ... </tex> şi negaţiile lor <tex> \sim A </tex>, <tex> \sim B </tex> <tex> ... </tex> iar muchiile acestui graf vor fi implicaţiile echivalente cu propoziţiile din expresie. Deci, dacă expresia are $M$ propoziţii, graful va avea $2M$ muchii. Acestea fiind zise, expresiei <tex> (\sim A \vee \sim B) \wedge (B \vee \sim C) \wedge (B \vee C) \wedge (\sim B \vee \sim D) \wedge (C \vee D) </tex> îi corespunde graful:

Fiecare clauză <tex> A \vee B </tex> poate fi scrisă ca două implicaţii <tex> (\sim A \rightarrow B) </tex> şi <tex> (\sim B \rightarrow A) </tex>. Realizăm un graf al implicaţiilor. Astfel, nodurile grafului vor fi variabilele <tex> A </tex>, <tex> B </tex> <tex> ... </tex> şi negaţiile lor <tex> \sim A </tex>, <tex> \sim B </tex> <tex> ... </tex> iar muchiile acestui graf vor fi implicaţiile echivalente cu propoziţiile din expresie. Deci, dacă expresia are $M$ propoziţii, graful va avea $2M$ muchii. Acestea fiind zise, expresiei <tex> (\sim A \vee \sim B) \wedge (B \vee \sim C) \wedge (B \vee C) \wedge (\sim B \vee \sim D) \wedge (C \vee D) </tex> îi corespunde graful:

p=. !2-sat?Graf.png!

Dacă avem <tex> A \longrightarrow B </tex> o muchie în graful nostru şi literalul <tex> A </tex> este adevărat, atunci şi literalul <tex> B </tex> trebuie să fie adevărat pentru ca propoziţia reprezentată de muchie să fie satisfăcută. Putem demonstra prin inducţie că dacă există un drum în graf de la literalul <tex> A </tex> la literalul <tex> B </tex>, atunci dacă <tex> A </tex> este adevărat şi <tex> B </tex> trebuie să fie adevărat. Dacă există un drum de la un literal <tex> X </tex> la <tex> \sim X </tex>, precum şi un drum invers, atunci nu va exista soluţie pentru că nu putem seta în acelaşi timp o variabilă şi valoarea ei negată la valoarea adevărat. De aici rezultă că dacă în graful asociat expresiei există o variabilă <tex> X </tex> în aceeaşi componentă tare conexă cu <tex> \sim X </tex> atunci instanţa problemei satisfiabilităţii nu poate fi satisfăcută. Dacă nu există o asemenea variabilă, vom vedea în continuare cum putem rezolva problema. Întâi, facem observaţia că dacă în graf există muchia <tex> A \longrightarrow B </tex> atunci există şi muchia <tex> \sim B \longrightarrow \sim A </tex>. Astfel, dacă există un drum de la <tex> A </tex> la <tex> B </tex> în graf, aplicând proprietatea menţionată pentru fiecare muchie a drumului, vom găsi un drum de la <tex> \sim B </tex> la <tex> \sim A </tex>. Evident, afirmaţia este valabilă şi reciproc: dacă există drum de la <tex> B </tex> la <tex> A </tex> atunci vom avea un drum de la nodul <tex> \sim A </tex> la <tex> \sim B </tex>. Astfel, dacă avem că <tex> A </tex> şi <tex> B </tex> sunt în aceeaşi componentă tare conexă atunci şi nodurile <tex> \sim A </tex> şi <tex> \sim B </tex> sunt în aceeaşi componentă tare conexă. Deci, dacă nu există doi literali <tex> X </tex> şi <tex> \sim X </tex> în aceeaşi componentă tare conexă, putem să împărţim graful în componente tare conexe şi să împerechem componentele câte două astfel ca în fiecare pereche să apară o componentă <tex> U </tex> cu nişte literali şi altă componentă <tex> \sim U </tex> cu aceiaşi literali negaţi. Pentru a găsi o soluţie vom determina mai întâi componentele tare conexe ale grafului. Apoi putem contracta fiecare componentă într-un nod. Graful obţinut va fi aciclic. Alegem un nod <tex> u </tex> în care nu intră nicio muchie (un asemenea nod trebuie să existe pentru a nu exista cicluri). Din considerente de simetrie, din nodul lui pereche <tex> \sim u </tex> nu va ieşi nicio muchie. Literalilor componentei <tex> U </tex> putem să le dăm valoarea de adevăr <tex> 0 </tex>, iar literalilor din componenta pereche <tex> \sim U </tex>  putem să le dăm valoarea de adevăr <tex> 1 </tex>. Această alegere nu impune restricţii asupra celorlalţi literali şi elimină câteva variabile din problemă. Repetarea recursivă a acestui pas pe graful rămas va duce la rezolvarea problemei. Determinarea componentelor tare conexe se poate face în complexitatea $O(N + M)$. Pentru a vedea acest algoritm puteţi consulta 'secţiunea $23.5$':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm din {'[1]':2-sat#bibliografie}. Iar eliminarea nodurilor de care vorbeam mai sus se poate face în $O(N + M)$ folosind o sortare topologică.

Dacă avem <tex> A \longrightarrow B </tex> o muchie în graful nostru şi literalul <tex> A </tex> este adevărat, atunci şi literalul <tex> B </tex> trebuie să fie adevărat pentru ca propoziţia reprezentată de muchie să fie satisfăcută. Putem demonstra prin inducţie că dacă există un drum în graf de la literalul <tex> A </tex> la literalul <tex> B </tex>, atunci dacă <tex> A </tex> este adevărat şi <tex> B </tex> trebuie să fie adevărat. Dacă există un drum de la un literal <tex> X </tex> la <tex> \sim X </tex>, precum şi un drum invers, atunci nu va exista soluţie pentru că nu putem seta în acelaşi timp o variabilă şi valoarea ei negată la valoarea adevărat. De aici rezultă că dacă în graful asociat expresiei există o variabilă <tex> X </tex> în aceeaşi componentă tare conexă cu <tex> \sim X </tex> atunci instanţa problemei satisfiabilităţii nu poate fi satisfăcută. Dacă nu există o asemenea variabilă, vom vedea în continuare cum putem rezolva problema. Întâi, facem observaţia că dacă în graf există muchia <tex> A \longrightarrow B </tex> atunci există şi muchia <tex> \sim B \longrightarrow \sim A </tex>. Astfel, dacă există un drum de la <tex> A </tex> la <tex> B </tex> în graf, aplicând proprietatea menţionată pentru fiecare muchie a drumului, vom găsi un drum de la <tex> \sim B </tex> la <tex> \sim A </tex>. Evident, afirmaţia este valabilă şi reciproc: dacă există drum de la <tex> B </tex> la <tex> A </tex> atunci vom avea un drum de la nodul <tex> \sim A </tex> la <tex> \sim B </tex>. Astfel, dacă avem că <tex> A </tex> şi <tex> B </tex> sunt în aceeaşi componentă tare conexă atunci şi nodurile <tex> \sim A </tex> şi <tex> \sim B </tex> sunt în aceeaşi componentă tare conexă. Deci, dacă nu există doi literali <tex> X </tex> şi <tex> \sim X </tex> în aceeaşi componentă tare conexă, putem să împărţim graful în componente tare conexe şi să împerechem componentele câte două astfel ca în fiecare pereche să apară o componentă <tex> U </tex> cu nişte literali şi altă componentă <tex> \sim U </tex> cu aceiaşi literali negaţi. Pentru a găsi o soluţie vom determina mai întâi componentele tare conexe ale grafului. Apoi putem contracta fiecare componentă într-un nod. Graful obţinut va fi aciclic. Alegem un nod <tex> u </tex> în care nu intră nicio muchie (un asemenea nod trebuie să existe pentru a nu exista cicluri). Din considerente de simetrie, din nodul lui pereche <tex> \sim u </tex> nu va ieşi nicio muchie. Literalilor componentei <tex> U </tex> putem să le dăm valoarea de adevăr <tex> 0 </tex>, iar literalilor din componenta pereche <tex> \sim U </tex>  putem să le dăm valoarea de adevăr <tex> 1 </tex>. Această alegere nu impune restricţii asupra celorlalţi literali şi elimină câteva variabile din problemă. Repetarea recursivă a acestui pas pe graful rămas va duce la rezolvarea problemei. Determinarea 'componentelor tare conexe':problema/ctc se poate face în complexitatea $O(N + M)$. Pentru a vedea acest algoritm puteţi consulta 'secţiunea $23.5$':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm din {'[1]':2-sat#bibliografie}. Iar eliminarea nodurilor de care vorbeam mai sus se poate face în $O(N + M)$ folosind o 'sortare topologică':problema/sortaret.

Să urmărim cum merge algoritmul nostru pe exemplul de mai sus. Componentele tare conexe sunt următoarele: <tex> \{A\} </tex>, <tex> \{\sim A\} </tex>, <tex> \{B, C, \sim D\} </tex>, <tex> \{\sim B, \sim C, D\} </tex>. În nodul asociat componentei <tex> \{A\} </tex> nu intră nicio muchie. Astfel, putem să îi atribuim lui <tex> A </tex> valoarea <tex> 0 </tex>, iar după eliminarea lui <tex> \{A\} </tex> şi <tex> \{\sim A\} </tex>în nodul asociat componentei <tex> \{\sim B, \sim C, D\} </tex> nu intră nicio muchie, deci putem să îi atribuim lui <tex> B </tex> valoarea <tex> 1 </tex>, lui <tex> C </tex> valoarea <tex> 1 </tex> şi lui <tex> D </tex> valoarea <tex> 0 </tex>. Această atribuire este satisfiabilă după cum vedem în continuare: