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.

$\endgroup$
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.

$\endgroup$
14
$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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