<p>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. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.431.5794&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Self-Reducibility of Hard Counting Problems
with Decision Version in P</a></p>

CC BY-SA 3.0
2017-05-13T17:12:04.180Z
2017-05-13T17:12:04.180Z
Tayfun Pay
<p>This is still #P-complete [1]. 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).</p>

<p>[1] Roth, Dan. "On the hardness of approximate reasoning." Artificial Intelligence 82.1-2 (1996): 273-302.</p>

CC BY-SA 3.0
2017-05-13T17:01:35.903Z
2017-05-13T17:01:35.903Z
holf
<p>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 <a href="https://en.wikipedia.org/wiki/Sharp-P-complete" rel="noreferrer">#P-complete</a> problem.</p>

<p>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.</p>

<sat><counting-complexity><polynomial-time><monotone>
Counting the number of satisfying assignments in a POSITIVE CNF-SAT
Mohemnist
# Counting the number of satisfying assignments in a POSITIVE CNF-SAT

(Asked by: username_0 on 2017-05-13)

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](https://en.wikipedia.org/wiki/Sharp-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.

**Tags:** sat, counting-complexity, polynomial-time, monotone


---

## 2 answers

### Answer by username_2 on 2017-05-13. Score: 20 | Accepted answer

This is still #P-complete [1]. 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).

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


---

### Answer by username_1 on 2017-05-13. Score: 15

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.431.5794&rep=rep1&type=pdf)


---

