_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. Iată pe scurt cum se procedează. În primul rând, graful va fi împărţit în 'componente tare-conexe':problema/ctc. O proprietate importantă a componentelor conexe este că în fiecare componentă există un ciclu ce conţine toate vârfurile sale. Astfel, toate nodurile dintr-o componentă tare conexă vor avea, în mod necesar, aceeaşi valoare de adevăr. Dacă nu ar fi astfel, ar exista pe ciclu o valoare „true” ce ar implica o valoare „false”. Observăm că dacă un nod şi negaţia sa se găsesc în aceeaşi componentă tare conexă atunci nu există soluţie. Din câteva proprietăţi de simetrie, pe care le puteţi găsi în articol, se deduce că pentru o componentă <tex> c </tex> în care se găseşte o implicaţie <tex> x_{i} \rightarrow x_{j} </tex>, va exista o componentă <tex> \bar{c} </tex> ce va conţine implicaţia echivalentă <tex> \bar{x_{j}} \rightarrow \bar{x_{i}} </tex>. În continuare, vom contracta componentele tare-conexe într-un nod, rezultând un graf orientat aciclic. În acest graf, utilizând o 'sortare topologică':problema/sortaret vom împerechea succesiv nodurile după cum urmează. Se va alege un nod cu gradul de intrare zero. Din nodul său pereche, datorită simetriei de care aminteam, nu va ieşi nicio muchie. Astfel, toate valorile din componenta tare conexă asociată nodului 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 variabile. Ulterior, se vor elimina cele două noduri şi se va relua procedeul.

În articolul de mai sus se arată cum se ajunge la soluţie. Iată pe scurt cum se procedează. În primul rând, graful va fi împărţit în 'componente tare-conexe':problema/ctc. O proprietate importantă a componentelor conexe este că în fiecare componentă există un ciclu ce conţine toate vârfurile sale. Astfel, toate nodurile dintr-o componentă tare conexă vor avea, în mod necesar, aceeaşi valoare de adevăr. Dacă nu ar fi astfel, ar exista pe ciclu o valoare „true” ce ar implica o valoare „false”. Observăm că dacă un nod şi negaţia sa se găsesc în aceeaşi componentă tare conexă atunci nu există soluţie. Din câteva proprietăţi de simetrie, pe care le puteţi găsi în articol, se deduce că pentru o componentă <tex> c </tex> în care se găseşte o implicaţie <tex> x_{i} \rightarrow x_{j} </tex>, va exista o componentă <tex> \bar{c} </tex> ce va conţine implicaţia echivalentă <tex> \bar{x_{j}} \rightarrow \bar{x_{i}} </tex>. În continuare, vom contracta componentele tare-conexe într-un nod, rezultând un graf orientat aciclic. Prin gradul unei componente tare-conexe vom înţelege gradul nodului asociat din acest graf orientat aciclic. Utilizând o 'sortare topologică':problema/sortaret vom împerechea succesiv componentele după cum urmează. Se va alege o componentă cu gradul de intrare zero. Din componenta sa pereche, datorită simetriei de care aminteam, nu va ieşi nicio muchie. Astfel, toate nodurile din componenta tare-conexă cu gradul de intrare zero vor avea valoarea de adevăr „false”, pentru a nu impune restricţii asupra celorlalte noduri, 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 alte valori. Ulterior, se vor elimina cele două noduri şi se va relua procedeul.

Soluţia de '100 de puncte':job_detail/382602?action=view-source are complexitatea $O(M + N)$.