Question

As per the title, is there any polynomial time algorithm to count the number of satisfying arguments for a 2SAT expression with pure literals? An even shallower case: Is there any such counter when the literals in the expression are either all positive, or all negative?

Was it helpful?

Solution

Counting the number of satisfying assignments in a positive 2SAT formula is the same as counting the number of vertex covers in the corresponding graph (after removing singleton clauses). Counting the number of vertex covers is known to be $\mathsf{\#P}$-complete. See also this question on cstheory.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top