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
 
//TODO: Solutia in O(M + N)
 
Pentru o demonstratie a functionalitatii acestui algoritm consultati 'articolul':/2-sat#solutie-3

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

*Marius* Cezar, scuze că îţi zic puţin târziu, dar, din punctul meu de vedere nu mai e nevoie să explici în detaliu soluţiile. Sunt deja prezentate în articolul lui Cosmin. Câte cuvinte despre fiecare (cum e la ultima cu algoritmul randomizat) şi o sursă beton sunt de ajuns. Dar să fie beton sursa. :)