====== JFIZO - Zadanie 09.089 ======

Pokażemy, że $3SAT <_p STASI$.

===== Redukcja =====

Liczba $k$ w $STASI$ to liczba zmiennych w formule.

Tworzymy graf:
  * dla każdej zmiennej $p_i$ w $3SAT$ tworzymy 3 wierzchołki: $p_i, \neg p_i, q_i$,
  * dokładamy krawędzie: $\{p_i,\neg p_i\}, \{p_i, q_i\}, \{\neg p_i, q_i\}$,
  * dla klauzuli o numerze $i$ tworzymy wierzchołek $v_i$ z krawędziami do literałów,\\ jakie ma w sobie, np. $p_1 \vee \neg p_2 \vee p_3$ ma krawędzie: $\{v_i ,p_1\}, \{v_i, \neg p_2\}, \{v_i, p_3\}$.

===== Dlaczego to działa? =====

Rozstawiamy agentów po wierzchołkach $p_i$ albo $\neg p_i$. Agent na literale oznacza wartość $True$.

Co się stanie, jak ustawimy agenta gdzieś indziej?
  - Agent na $v_i$. Jeżeli chociaż jednego agenta ustawimy na klauzuli, to nie mamy jak nadzorować któregoś wierzchołka $q_i$,\\ ponieważ mamy $k$ agentów i $k$ wierzchołków $q_i$.
  - Agent na $q_i$. Jeżeli agenta ustawimy na wierzchołku $q_i$, to może on nie nadzorować klauzuli, dla której jest kluczowy.\\ Jeżeli tak jest można go przestawić w inne miejsce. Jeżeli formuła jest niezależna od którejś zmiennej $p_i$, to wtedy agent może stać na $q_i$.
  - Agenci stoją jednocześnie na $p_i$ oraz $\neg p_i$. Wtedy któryś z $q_i$ jest nienadzorowany, bo brak nam agentów.

Co się dzieje, jak agenci są na wierzchołkach $p_i$ albo $\neg p_i$?
  * każdy wierzchołek $q_i$ jest nadzorowany - krawędzie $\{q_i, p_i\}, \{q_i, \neg p_i\}$,
  * każdy wierzchołek $p_i$ oraz $\neg p_i$ jest nadzorowany - krawędzie $\{p_i, \neg p_i\}$,
  * jeżeli istnieje wartościowanie, że formuła jest spełnialna, to istnieje też takie rozstawienie agentów po literałowych wierzchołkach,\\ że każda klauzula jest nadzorowana.

===== Dowód =====

$(\Rightarrow)$ Skoro $\phi$ jest spełnialna, to istnieje takie wartościowanie $\sigma$, że $\hat{\sigma}(\phi) = \top$. \\ W grafie $f(\phi)$ możemy rozstawić $k$ agentów po wierzchołkach $p_i$ oraz $\neg p_i$ tak, że jeżeli $p_i$ jest prawdziwe w $\sigma$, to stawiamy tam agenta,\\ w przeciwnym wypadku stawiamy agenta na $\neg p_i$. Widać, że każde $q_i, p_i, \neg p_i$ będzie nadzorowane, oraz każdy wierzchołek odpowiadający klauzuli również będzie nadzorowany,\\ bo przy tym wartościowaniu była ona prawdziwa w $\phi$.

$(\Leftarrow)$ Skoro $f(\phi)$ ma dobre rozstawienie, to znaczy, że dla każdego $i$ agent stoi na jednym z $\{p_i, q_i, \neg p_i\}$.\\ Skonstruujemy wartosciowanie $\sigma$ tak, że jeżeli agent stoi na $p_i$ lub $q_i$, to $\sigma(p_i)=\top$, a w przeciwnym przypadku $\sigma(p_i)=\bot$.\\ Widać teraz, że dla takiego wartościowania $\phi$ jest prawdziwa, bo każda klauzula jest nadzorowana,\\ czyli w każdej klauzuli co najmniej jeden literał jest prawdziwy.