Polynomial time counter of solutions of 2SAT expression with pure literals
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?
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