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

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

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

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

== code(cpp) |
atribuim valori booleene arbitrare variabilelor;

cât timp expresia nu este satisfăcută execută

cât timp expresia nu este satisfăcută, execută

    găsim o propoziţie cu valoarea de adevăr 0;
    schimbăm valoarea de adevăr a oricăreia dintre cele două variabile prezente în propoziţie;

sfcâttimp

sfârşit cât timp

==
Linia $4$ va face ca acea propoziţie să aibă noua valoare de adevăr <tex> 1 </tex>.
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':http://en.wikipedia.org/wiki/Hamming_distance î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:

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

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

<tex> T(i) \le (T(i + 1) + T(i - 1)) / 2 + 1 </tex> pentru $0 < i < N$ ({$N$} e numărul de variabile booleene ale expresiei)

<tex> T(i) \le \frac {T(i + 1) + T(i - 1)}{2} + 1 </tex> pentru $0 < i < N$ ({$N$} e numărul de variabile booleene ale expresiei)

Se pune semnul de inegalitate pentru că ambele variabile pot avea valori diferite faţă de cele din soluţie, deci schimbarea valorii oricăreia ar putea să ne aducă mai aproape de soluţie.

Pentru că dacă toate variabilele diferă de soluţie, orice schimbare ne aduce mai aproape de soluţie:

Dacă toate variabilele diferă de soluţie, orice schimbare ne aduce mai aproape de aceasta:

<tex> T(N) = T(N - 1) + 1 </tex>
Ne interesează numai limitele superioare, deci folosim doar egalităţi în loc de inegalităţi:

<tex> X(0) = 0, X(i) = (X(i + 1) + X(i - 1))/2 + 1, X(N) = X(N - 1) + 1 </tex>

<tex> X(0) = 0 </tex>, <tex> X(i) = \frac {X(i + 1) + X(i - 1)}{2} + 1 </tex>, <tex> X(N) = X(N - 1) + 1 </tex>

Dacă adunăm toate ecuaţiile obţinem:

<tex> X(0) + X(1) + ... + X(N) </tex> <tex> = (X(0) + X(1) + 2X(2) + ... + 2X(N - 2) + X(N - 1) + X(N))/2 + X(N) + N-1 </tex>

<tex> X(0) + X(1) + ... + X(N) = </tex> <tex> \frac {X(0) + X(1) + 2X(2) + ... + 2X(N - 2) + X(N - 1) + X(N)}{2} + X(N) + N - 1 </tex>

De aici avem că <tex> (X(1) + X(N - 1) - X(N)) / 2 = N - 1 </tex>, din <tex> X(N) = X(N - 1) + 1 </tex> avem <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4n - 2 ... X(i) = 2iN - i </tex> de unde, când <tex> i = N </tex> avem că <tex> X(N) = 2N^2 - N </tex>.

De aici avem că <tex> \frac {X(1) + X(N - 1) - X(N)}{2} = N - 1 </tex>, iar din <tex> X(N) = X(N - 1) + 1 </tex> rezultă că <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4N - 4 </tex> <tex> ... </tex> <tex> X(i) = 2iN - i^2 </tex>, de unde, când <tex> i = N </tex>, avem că <tex> X(N) = N^2 </tex>.

Astfel, numărul mediu de paşi ai algoritmului este $2N^2^ - N$ iar dacă aplicăm algoritmul în mod aleator de mai multe ori avem o probabilitate foarte mare să ajungem la rezultat.

Astfel, numărul mediu de paşi ai algoritmului este pătratic în numărul $N$ de variabile. Lăsând algoritmul să ruleze de 2-3 ori mai mulţi paşi decât numărul mediu, avem o probabilitate foarte mare să ajungem la rezultat.

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