atribuim valori booleene arbitrare variabilelor;
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;  // ceea ce va face ca acea propoziţie să aibă noua valoare de adevăr 1;

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

sfcâttimp
==

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