JFiZO - Lista 9
JFIZO - Zadanie 09.088
Każdą klauzę z 5CNF zamieniamy osobno.
Mamy C = a \vee b \vee c \vee d \vee e. Dodajemy dwie nowe zmienne logiczne y_1 i y_2. Z C tworzymy C' = (a \vee b \vee y_1) \wedge (\neg y_1 \vee c \vee y_2) \wedge (\neg y_2 \vee d \vee e).
Dowód. Załóżmy, że istnieje wartościowanie, które spełnia tę formułę 5CNF. Każda klauzula musi zostać spełniona, zatem w każdej klauzuli istnieje co najmniej jeden literał, który jest spełniony przez to wartościowanie. W takim wypadku ustawiamy odpowienio wartościowania y_1 i y_2.
W drugą stronę należy zauważyć, że samymi y_1 i y_2 nie spełnimy wszystkich trzech klauzul naraz, zatem któryś literał musi zostać spełniony.
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.
JFiZO - Zadanie 09.93
Weźmy \phi \in 3CNF.
Dla każdej zmiennej x_i w formule \phi, która wystepuje więcej niż 3 razy, zamień jej wystąpienia na dodatkowe zmienne: y_{x_i,1},\cdots ,y_{x_i,k} gdzie k to liczba wystąpień tej zmiennej.
Zapewnij, że wszystkie nowe zmienne są tak samo wartościowane: y_{x_i,1} ⇒ y_{x_i,2} ⇒ … ⇒ y_{x_i,k} ⇒ y_{x_i,1} (dodajemy te implikacje parami do naszej formuly). Dla każdego zanegowanego wystąpienia zmiennej, w formule zawierajacej implikacje przed nową zmienną obrazującą to wystąpienie zmiennej x_i, dodajemy negację.
