13
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
20
$\begingroup$

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.

Improve this answer
$\endgroup$
15
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.