Wykazać kompletność NP decydującej o satysfakcji monotonicznej formuły boolowskiej

Próbuję rozwiązać ten problem i naprawdę walczę.

Monotoniczne logiczna wzór jest wzorem w zdań logiki, gdy wszystkie literałami dodatnie. Na przykład,

$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$

jest monotoniczną funkcją logiczną. Z drugiej strony coś takiego

$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$

nie jest monotoniczną funkcją logiczną.

Jak mogę udowodnić kompletność NP dla tego problemu:

Określić, czy monotoniczna funkcja boolowska jest zadowalająca, jeśli zmiennych lub mniej są ustawione na 1 ?$k$$1$

Oczywiście wszystkie zmienne można po prostu ustawić jako dodatnie, a to trywialne, dlatego istnieje ograniczenie dodatnio ustawionych zmiennych.$k$

$\neg x_1$$z_1$$x_1$$z_1$

$k$

Ograniczenie do formuł monotonicznych jest w rzeczywistości zaskakująco łatwe do wykazania twardości, po prostu musisz przez chwilę wyjść poza problemy satysfakcji. Zamiast próbować modyfikować instancję SAT, zamiast tego zaczynamy od Dominating Set (DS).

Sprawdź, czy możesz go zdobyć stamtąd. Więcej jest w spoilerach, podzielonych na kawałki, ale unikaj ich, jeśli możesz. Nie pokażę członkostwa w NP, nie powinieneś mieć z tym problemu.

$(G, k)$$k$$G$$(\phi,k)$$\phi$

Podstawowa konstrukcja:

$v\in V(G)$$v' \in \text{var}(\phi)$$v \in V(G)$$c_{v} = \bigvee_{u\in N(v)} u'$

Szkic dowodu:

$k$$k$$\phi$$k$$c_{v}$$v$

$z_i$$\neg x_i$$\phi$$\phi'$$\neg x_i$$z_i$$x_i \vee z_i$$k$$\phi'$$\phi$$k$$x_i \vee z_i$$\phi'$$k$$k$