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, transformand astfel problema intr-una de grafuri, care se poate rezolva determinand compomentele tare-conexe.

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