JFIZO - Zadanie 09.089

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

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\}.

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?

1. 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.
2. 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.
3. 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.

(\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.