O alta solutie neoptima, in complexitatea $O(N^2^)$ se bazeaza pe un algoritm randomizat. Initial se atribuie valori arbitrare variabilelor, iar apoi cat timp expresia nu este satisfacuta se gaseste o propozitie cu valoarea de adevar $0$ si se schimba valoarea unuia dintre cei 2 termeni componenti ai propozitiei.

Solutia optima, in complexitatea $O(M + N)$ se foloseste de relatia de implicatie, transformand astfel problema intr-una de grafuri, care se poate rezolva determinand 'compomentele tare-conexe':/problema/ctc.

Solutia optima, in complexitatea $O(M + N)$ se foloseste de 'relatia de implicatie':http://en.wikipedia.org/wiki/Logical_implication, transformand astfel problema intr-una de grafuri, care se poate rezolva determinand 'componentele tare-conexe':/problema/ctc.

Pentru mai multe detalii in legatura cu solutiile consultati 'articolul':/2-sat.