# Counting the number of satisfying assignments in a POSITIVE CNF-SAT

We know the problem of counting the number of satisfying assignment in a given general boolean formula (CNF-SAT), a given DNF formula, or even a given 2SAT formula is a #P-complete problem.

Now, consider a CNF-SAT with no negative literal (no $\neg A$, always $A$). The decision problem is very easy (set all of the variables to TRUE and check if the assignment is satisfying the formula), but what about counting the number of satisfying assignments? Does this have a polynomial time algorithm? Or it's a #P-complete problem.

## 2 Answers

This is still #P-complete . This problem is usually referred to as montone (#)SAT. Monotone #2-SAT is already #P-complete (this is equivalent to counting vertex covers of a graph).

 Roth, Dan. "On the hardness of approximate reasoning." Artificial Intelligence 82.1-2 (1996): 273-302.

This problem is Monotone-SAT. It is #P-Complete under Cook Reductions. It is one of those problems that are "easy to decide but hard to count." I recommend the following paper. Self-Reducibility of Hard Counting Problems with Decision Version in P