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

12

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,

(x1x2)(x1x3)(x3x4x5)

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

(x1x2x3)(¬x1x3)(¬x1x5)

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 ?k1

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

¬x1z1x1z1

nat
źródło
Witamy! Zachowaj większą ostrożność w przypadku języka i formatowania.
Raphael

Odpowiedzi:

12

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)kG(ϕ,k)ϕ

Podstawowa konstrukcja:

vV(G)vvar(ϕ)vV(G)cv=uN(v)u

Szkic dowodu:

kkϕkcvv

Luke Mathieson
źródło
Wow, to ma o wiele więcej sensu, dziękuję! Myślę, że zdecydowanie byłem przyłapany na próbach zredukowania SAT do monotonnej formuły boolowskiej.
nat
Widzę również, że możemy również zmniejszyć pokrycie wierzchołków do monotonicznej formuły boolowskiej.
nat
1
k
Myślę, że dokładnie to samo podejście działa z pokryciem wierzchołków.
Haskell Fun
@HaskellFun, też o tym myślałem. Pokrywa wierzchołka jest taka sama jak monotonowy Min-W2SAT.
rus9384
2

zi¬xiϕϕ¬xizixizikϕϕkxiziϕkk

David
źródło