h2. Soluţii pentru 2-SAT

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 <tex> 1 </tex>.

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

h3. Soluţie $O(M * 2^N^)$

sfcâttimp
==

De ce ar merge acest algoritm? Să presupunem că există o soluţie a problemei, o notăm cu <tex> S </tex>, iar cu <tex> X </tex> notăm şirul valorilor curente ale variabilelor. Ne uităm la fiecare pas al algoritmului la numărul de variabile care au valori diferite în soluţie faţă de cele din <tex> X </tex> (acest număr de diferenţe între elementele de acelaşi index pentru două şiruri se mai numeşte şi $distanţă Hamming$ între şiruri). Fie această valoare la pasul current $K$. Noi am vrea să avem $K = 0$. Cum va evolua $K$ pe parcursul algoritmului? La un moment dat noi schimbăm valoarea unei variabile luate aleator dintr-o propoziţie nesatisfăcută. Pentru că în <tex> S </tex> propoziţia este satisfăcută, înseamnă că cel puţin una dintre cele două variabile ale propoziţiei are valori diferite în <tex> X </tex> faţă de <tex> S </tex>. Astfel, operaţia făcută de noi are probabilitate de cel puţin $0.5$ să ne aducă mai aproape de soluţie. Vom nota cu <tex> T(i) </tex> numărul probabil de paşi în care un şir <tex> X </tex> aflat la $distanţa Hamming$ egală cu $i$ faţă de <tex> S </tex>, va fi transformat în <tex> S </tex>. Evident:

De ce ar merge acest algoritm? Să presupunem că există o soluţie a problemei, o notăm cu $S$, iar cu $X$ notăm şirul valorilor curente ale variabilelor. Ne uităm la fiecare pas al algoritmului la numărul de variabile care au valori diferite în soluţie faţă de cele din $X$ (acest număr de diferenţe între elementele de acelaşi index pentru două şiruri se mai numeşte şi $distanţă Hamming$ între şiruri). Fie această valoare la pasul current $K$. Noi am vrea să avem $K = 0$. Cum va evolua $K$ pe parcursul algoritmului? La un moment dat noi schimbăm valoarea unei variabile luate aleator dintr-o propoziţie nesatisfăcută. Pentru că în $S$ propoziţia este satisfăcută, înseamnă că cel puţin una dintre cele două variabile ale propoziţiei are valori diferite în $X$ faţă de $S$. Astfel, operaţia făcută de noi are probabilitate de cel puţin $0.5$ să ne aducă mai aproape de soluţie. Vom nota cu <tex> T(i) </tex> numărul probabil de paşi în care un şir $X$ aflat la $distanţa Hamming$ egală cu $i$ faţă de $S$, va fi transformat în $S$. Evident:

<tex> T(0) = 0 </tex>.