sfcâttimp
==

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>.
 
<tex> T(i) \le (T(i + 1) + T(i - 1)) / 2 + 1 </tex>
 
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:
 
<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>
 
Dacă adunăm toate ecuaţiile obţinem:
 
<tex> X(0) + X(1) + ... + X(N) = (X(0) + X(1) + 2X(1) + … + 2X(N - 2) + X(N - 1) + X(N)) / 2 + N + X(N - 1) </tex>
 
De aici avem că <tex> (X(1) + X(N) - X(N - 1)) / 2 = N </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 - 4 ... X(i) = 2iN - i^2^ </tex> de unde, când <tex> i = N </tex> avem că <tex> X(N) = N^2^ </tex>.