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,
jest monotoniczną funkcją logiczną. Z drugiej strony coś takiego
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 ?
Oczywiście wszystkie zmienne można po prostu ustawić jako dodatnie, a to trywialne, dlatego istnieje ograniczenie dodatnio ustawionych zmiennych.
Odpowiedzi:
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.
Podstawowa konstrukcja:
Szkic dowodu:
źródło
źródło