h2(#introducere). Introducere

Problema satisfiabilităţii, notată prescurtat cu $SAT$, cere determinarea existenţei pentru o formulă booleană <tex> \phi </tex> a unei artibuiri satisfiabile. O formulă booleană <tex> \phi </tex> este compusă din $variabile$ logice <tex> (x_{1}, x_{2}, ...) </tex>, $operatori$ logici ( <tex> \wedge </tex> şi,  <tex> \vee </tex> sau, <tex> \sim </tex> non, <tex> \rightarrow </tex> implicaţie şi <tex> \leftrightarrow </tex> echivalenţă), şi $paranteze$. O atribuire de valori booleene pentru variabilele acestei expresii se numeşte $atribuire satisfiabilă$ dacă evaluarea expresiei după atribuirea valorilor dă ca rezultat valoarea de adevăr $adevărat$. De acum încolo vom folosi pentru simplitate valorile <tex> 1 </tex> şi <tex> 0 </tex> în loc de $adevărat$ şi $fals$.

Problema satisfiabilităţii, notată prescurtat cu $SAT$, cere determinarea existenţei pentru o formulă booleană <tex> \phi </tex> a unei atribuiri satisfiabile. O formulă booleană <tex> \phi </tex> este compusă din $variabile$ logice <tex> (x_{1}, x_{2}, ...) </tex>, $operatori$ logici ( <tex> \wedge </tex> şi,  <tex> \vee </tex> sau, <tex> \sim </tex> non, <tex> \rightarrow </tex> implicaţie, <tex> \leftrightarrow </tex> echivalenţă), şi $paranteze$. O atribuire de valori booleene pentru variabilele acestei expresii se numeşte $atribuire satisfiabilă$ dacă evaluarea expresiei după atribuirea valorilor dă ca rezultat valoarea de adevăr $adevărat$. De acum încolo vom folosi pentru simplitate valorile <tex> 1 </tex> şi <tex> 0 </tex> în loc de $adevărat$ şi $fals$.

Un exemplu de formulă ar fi <tex> \phi = ((x_{1} \rightarrow x_{2}) \vee \sim((\sim x_{1} \leftrightarrow x_{3}) \vee x_{4})) \wedge \sim x_{2} </tex>. Aceasta are atribuirea satisfiabilă <tex> \langle x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1 \rangle </tex> pentru că <tex> \phi = ((0 \rightarrow 0) \vee \sim((\sim 0 \leftrightarrow 1) \vee 1)) \wedge \sim 0 = (1 \vee \sim (1 \vee 1)) \wedge 1 = (1 \vee 0) \wedge 1 = 1</tex>.

Orice formulă booleană poate fi transformată în două forme:

* $Forma normal conjunctivă$ în care expresia este exprimată ca o conjuncţie de propoziţii, iar fiecare propoziţie este formată din o disjuncţie de $literali$. Un $literal$ este o variabilă care poate fi sau nu negată. Un exemplu de expresie în forma normal conjunctivă ar fi: <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) \wedge (x_{3} \vee x_{2} \vee x_{4}) \wedge (\sim x_{1} \vee \sim x_{3} \vee \sim x_{4}) </tex> care are pe <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) </tex> ca primă propoziţie cu literalii <tex> x_{1} </tex>, <tex> \sim x_{1} </tex>, <tex> \sim x_{2} </tex>.

* $Forma normal conjunctivă$ în care expresia este exprimată ca o conjuncţie de propoziţii, iar fiecare propoziţie este formată dintr-o disjuncţie de $literali$. Un $literal$ este o variabilă care poate fi sau nu negată. Un exemplu de expresie în forma normal conjunctivă ar fi: <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) \wedge (x_{3} \vee x_{2} \vee x_{4}) \wedge (\sim x_{1} \vee \sim x_{3} \vee \sim x_{4}) </tex> care are pe <tex> (x_{1} \vee \sim x_{1} \vee \sim x_{2}) </tex> ca primă propoziţie cu literalii <tex> x_{1} </tex>, <tex> \sim x_{1} </tex>, <tex> \sim x_{2} </tex>.

* $Forma normal disjunctivă$ este formată ca o disjuncţie de propoziţii, fiecare dintre aceste propoziţii fiind o conjuncţie de literali. Un exemplu de o asemenea formulă ar fi următoarea: <tex> (x_{1} \wedge x_{2} \wedge x_{3}) \vee (x_{1} \wedge \sim x_{2} \wedge x_{3}) \vee (x_{1} \wedge \sim x_{2} \wedge \sim x_{3}) \vee (\sim x_{1} \wedge x_{2} \wedge \sim x_{2}) </tex>.
h2(#overview-sat). SAT, 3-SAT, 2-SAT

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 $3-SAT$, şi multe probleme pot fi demonstrate a fi $NP-complete$ prin reducerea la această problemă. Din fericire, problema $2-SAT$, 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 $2-SAT$ şi câteva aplicaţii ale acesteia la concursuri de programare.

Problema $SAT$ este $NP-completă$. De fapt, 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 $3-SAT$, şi multe probleme pot fi demonstrate a fi $NP-complete$ prin reducerea lui $3-SAT$ la problemele respective în timp polinomial. Din fericire, problema $2-SAT$, 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 $2-SAT$ şi câteva aplicaţii ale acesteia din concursuri de programare.

h2(#solutii-2-sat). Soluţii pentru 2-SAT

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

Dacă avem <tex> A \longrightarrow B </tex> o muchie în graful nostru, atunci dacă 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> 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 aceiaş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 tari 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 tari conexe ale grafului. Apoi putem contracta fiecare componentă într-un nod. Graful obţinut va fi acciclic. 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 tari conexe se poate face în complexitatea $O(N + M)$. Pentru a vedea acest algoritm puteţi consulta secţiunea '$23.5$ din [1]':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm. Iar eliminarea  nodurilor de care vorbeam mai sus se poate face în $O(N + M)$ folosind o 'sortare topologică':problema/sortaret.

Dacă avem <tex> A \longrightarrow B </tex> o muchie în graful nostru, atunci dacă 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> 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 aceiaş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 tari 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 tari conexe ale grafului. Apoi putem contracta fiecare componentă într-un nod. Graful obţinut va fi acciclic. 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 tari 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ă.

Să urmărim cum merge algoritmul nostru pe exemplul de mai sus. Componentele tari 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ă nici o muchie. Astfel, putem să îi atribuim lui <tex> A </tex> valoarea <tex> 0 </tex>, iar î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> 0 </tex> şi lui <tex> D </tex> valoarea <tex> 1 </tex>. Această atribuire este satisfiabilă după cum vedem în continuare:

h2(#aplicatii). Aplicaţii

Restul articolului va prezenta aplicaţii ale problemei $2-SAT$ la concursurile de programare.

Restul articolului va prezenta aplicaţii ale problemei $2-SAT$ din concursurile de programare.

h2(#party). 'Party':problema/party (preONI 2003/2004)