Liczenie liczby spełniających zadania w POZYTYWNYM CNF-SAT

13

Wiemy, że problem zliczania liczby spełniających przypisanie w danej ogólnej formule boolowskiej (CNF-SAT), danej formule DNF, a nawet danej formule 2SAT jest problemem # P-zupełnym .

Teraz rozważmy CNF-SAT bez literału ujemnego (no , zawsze ). Problem decyzyjny jest bardzo łatwy (ustaw wszystkie zmienne na PRAWDA i sprawdź, czy przypisanie spełnia formułę), ale co z policzeniem liczby spełniających przypisań? Czy ma to algorytm wielomianowy? Lub jest to problem # P-zupełny.A¬AA

Mohemnist
źródło

Odpowiedzi:

20

To wciąż # P-complete [1]. Ten problem jest zwykle określany jako montone (#) SAT. Monotone # 2-SAT jest już # P-complete (jest to równoważne zliczaniu pokryw wierzchołków wykresu).

[1] Roth, Dan. „O twardości przybliżonego rozumowania”. Artificial Intelligence 82.1-2 (1996): 273-302.

holf
źródło