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ă.
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ă. Aceasta solutie trebuie sa obtina $40$ de puncte, sursa se gaseste aici.
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. Pentru o demonstratie a functionalitatii acestui algoritm consultati 'articolul':/2-sat#solutie-3
//TODO: Solutia in O(M + N)
h3. Aplicatii
* 'Party':/problema/party
* 'Aladdin':/problema/aladdin
* 'Excursion':http://www.oi.edu.pl/download/boi-2001.pdf - Baltic Olympiad in Informatics, 2001
* 'Peaceful Commission':http://www.oi.edu.pl/php/show.php?ac=e100000&module=show&file=zadania/oi8/spokojna - Polish Olympiad in Informatics, 20
== include(page="template/taskfooter" task_id="2sat") ==
