O alta soluţie neliniară, în complexitatea $O(N^2^ * M)$, se bazează pe un algoritm randomizat. Iniţial, se atribuie valori arbitrare variabilelor, după care, cât timp expresia nu este satisfăcută, se găseşte o propoziţie cu valoarea de adevăr $0$ şi se schimbă valoarea unuia dintre cei doi termeni componenţi ai propoziţiei. Precizăm că această abordare se comportă foarte bine în practică, aşa că ar trebui să obţină 'circa $70$ de puncte':/job_detail/382684?action=view-source.

'Soluţia optimă':job_detail/382602?action=view-source, în complexitatea $O(M + N)$, se foloseşte de 'relaţia de implicaţie':http://en.wikipedia.org/wiki/Logical_implication ce transformă expresia într-un graf, care se poate rezolva determinând 'componentele tare-conexe':/problema/ctc şi o 'sortare topologică':problema/sortaret.

Soluţia optimă foloseşte 'relaţia de implicaţie':http://en.wikipedia.org/wiki/Logical_implication pentru a transforma expresia într-un graf după cum urmează: orice disjuncţie de literali <tex> x_{i} \vee x_{j} </tex> este echivalentă cu următoarele implicaţii <tex> \bar{x_{i}} \to x_{j} </tex> şi <tex> \bar{x_{j}} \to x_{i} </tex>. Vom construi un graf cu noduri din mulţimea <tex> \{x_{1}, x_{2}, .., x_{n}, \bar{x_{1}}, \bar{x_{2}}, .., \bar{x_{n}}\} </tex> astfel: pentru orice propoziţie <tex> x_{i} \vee x_{j} </tex> va exista muchie de la <tex> \bar{x_{i}} </tex> la <tex> x_{j} </tex> şi de la <tex> \bar{x_{j}} </tex> la <tex> x_{i} </tex>, după cum arată relaţiile de implicaţie echivalente.
 
În continuare, vom demonstra o modalitate de a atribui valori nodurilor din graf, şi, astfel, implicit variabilelor pentru a rezolva 2SAT. Legătura dintre rezolvarea acestei probleme şi valorile nodurilor este o relaţie de echivalenţă, după cum se demonstrează...
 
_Necesitatea_ dacă avem soluţie pentru expresia 2SAT, va trebui să demonstrăm că pentru toate muchiile din graf nu întâlnim situaţii în care avem muchie de la un nod „true” la un nod „false”. Dacă presupunem prin absurd că există o astfel de muchie, între un nod <tex> \bar{x_{i}} </tex> „true” (deci <tex> x_{i} </tex> „false”) şi <tex> x_{j} </tex> „false”, atunci muchia de la <tex> \bar{x_{i}} </tex> la <tex> x_{j} </tex> există în graf dacă şi numai dacă în forma normal conjunctivă apare disjuncţia <tex> x_{i} \vee x_{j} </tex>. Însă, <tex> x_{i} \vee x_{j} </tex> este „false” dacă ambele valori sunt „false”. Contradicţie!
 
_Suficienţa_ dacă fiecărei propoziţii <tex> x_{i} \vee x_{j} </tex> îi corespund două muchii <tex> \bar{x_{i}} \to x_{j} </tex> şi <tex> \bar{x_{j}} \to x_{i} </tex>, atunci, cum nu putem avea <tex> \bar{x_{i}} </tex> „true”, <tex> x_{j} </tex> „false” sau <tex> \bar{x_{j}} </tex> „true”, <tex> x_{i} </tex> „false”, nu vom avea nici <tex> x_{i} </tex> şi <tex> x_{j} </tex> simultan egale cu „false”. Astfel, propoziţia <tex> x_{i} \vee x_{j} </tex> este adevărată.
 
În articolul de mai sus se arată cum se ajunge la soluţie. Pe scurt, graful va fi împărţit în 'componente tare-conexe':problema/ctc. O proprietate importantă arată că toate nodurile dintr-o componentă tare conexă vor avea aceeaşi valoare de adevăr. Astfel, dacă un nod şi negaţia sa se găsesc în aceeaşi componentă tare conexă atunci nu există soluţie. Utilizând câteva proprietăţi de simetrie, pe care le puteţi găsi în articol, împreună cu o 'sortare topologică':problema/sortaret se vor împerechea succesiv componentele tare conexe astfel încât toate valorile din componenta tare conexă cu gradul de intrare zero vor avea valoarea de adevăr „false”, pentru a nu impune restricţii asupra celorlalte variabile, iar toate nodurile din componenta pereche vor primi valoarea de adevăr „true”, întrucât din aceasta nu mai iese nicio muchie şi astfel nu va influenţa valorile altor noduri. Ulterior, se vor elimina cele două componente şi se va relua procedeul.
 
Soluţia de '100 de puncte':job_detail/382602?action=view-source are complexitatea $O(M + N)$.

h2. Aplicaţii