h3. Indicatii pentru rezolvare

O solutie evidenta este incercarea celor $2^N^$ configuratii posibile pentru termenii expresiei si apoi verificarea lor, aceasta abordare ducand la o complexitate de $O(2^N^ * M)$

O solutie evidenta este incercarea celor $2^N^$ configuratii posibile pentru termenii expresiei si apoi verificarea lor, aceasta abordare ducand la o complexitate de $O(2^N^ * M)$. Cu aceasta complexitate se obtin 20 de puncte, iar o sursa demonstrativa se gaseste aici.
 
Următoarea soluţie pare trivială, dar găsirea acestui algoritm şi realizarea faptului că el rezolvă corect problema sunt mai grele decât impresia lăsată după citirea ei. Considerăm o propoziţie oarecare cu două variabile $p$ şi $q$, apoi una dintre ele, de exemplu $p$. Ii atribuim lui $p$ valoarea $0$. Pentru ca propoziţia respectivă să aibă $1$ valoarea de adevăr, atunci valoarea lui q trebuie fixată. Fixând si valoarea lui $q$, probabil si alte propoziţii ce conţin literalul $q$ vor avea celălalt literal fixat. Propagăm astfel o serie de schimbări. După ce toate schimbările forţate au fost făcute, propoziţiile rezultate vor fi de următoarele tipuri: $A SAU B$, $1 SAU 0$, $1 SAU 1$, $1 SAU B$. Propozitii de tipul $0 SAU B$ nu pot aparea, pentru ca toate schimbarile fortate au fost deja propagate. Dacă apare o propoziţie $0 SAU 0$ atunci alegerea făcută pentru valoarea lui p este greşită. Vom încerca şi alegerea opusă pentru p. Dacă ambele duc la o propoziţie de tip  atunci expresia nu poate fi satisfăcută. Propoziţiile de forma $1 SAU 0$, $1 SAU 1$, $1 SAU B$  pot fi ignorate. În acest fel am eliminat cel puţin o variabilă şi o propoziţie din expresie. Dacă expresia iniţială era satisfiabilă, atunci şi expresia din care s-au eliminat câteva propoziţii a rămas satisfiabilă. Continuând pe această idee obţinem un algoritm de complexitate O(N * M), pentru că la fiecare atribuire de valoare pentru o variabilă parcurgem şirul de propoziţii o dată.
 

== include(page="template/taskfooter" task_id="2sat") ==