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

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.$\neg A$$A$

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.

Ten problem to Monotone-SAT. Jest to # P-Complete w ramach Redukcji Cooka. Jest to jeden z tych problemów, które „łatwo jest podjąć decyzję, ale trudno je policzyć”. Polecam następujący artykuł. Samonapędzalność problemów z liczeniem trudnym w wersji decyzyjnej w P.