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
źródło