Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Short version.

The original proof that #2-SAT is #P-complete shows, in fact, that those instances of #2-SAT which are both monotone (not involving the negations of any variables) and bipartite (the graph formed by the clauses over the variables is a bipartite graph) are #P-hard. Thus, the two special cases #2-MONOTONE-SAT and #2-BIPARTITE-SAT are #P-hard. Are there other special cases which can be characterized in terms of 'natural' properties of the formula, which are also #P-hard?

Long version.

The problem #2-SAT is the task of computing — for a boolean formula $\phi$ consisting of the conjunction of several clauses, where each clause is a disjunction of two literals $x_j$ or $\bar x_j$ — the number of boolean strings $x \in \{0,1\}^n$ such that $\phi(x) = 1$. Finding out whether or not there exists such an $x$ is easy; but counting the number of solutions in general is #P-complete, as shown by Valiant in The Complexity of Enumeration and Reliability Problems, SIAM J. Comput., 8, pp. 410–421.

For the case of #2-SAT in particular, what Valiant actually shows is a reduction to #2-SAT from counting matchings (including imperfect ones) in bipartite graphs, which gives rise to instances of #2-SAT with a very particular structure, as follows.

  1. First, note that the monotone problem is equivalent, by substitution, to the problem in which for each variable $x_j$, either $x_j$ occurs in the formula $\phi$ or $\bar x_j$ does but not both. In particular, the "monotone decreasing" problem in which only the negations $\bar x_j$ occur for every variable is exactly as hard as the monotone case.

  2. For any graph $G = (V,E)$ with $m$ edges, we can construct a monotone-decreasing 2-SAT formula corresponding to matchings — collections of edges which do not share any vertices — by assigning a variable $x_e$ to each edge, representing whether it is included in an edge-set; the property of a set $M \subseteq E$ being a matching is equivalent to the incidence vector $\mathbf x = \chi_M$ satisfying the CNF formula $\phi$ whose clauses are given by $(\bar x_e \vee \bar x_f)$ for every pair of edges $e, f \in E$ which share a vertex. By construction, $\phi$ has as many satisfying solutions $\mathbf x \in \{0,1\}^m$ as there are (possibly imperfect) matchings in the graph $G$.

  3. If the graph $G$ for which we want to count the matchings is bipartite, then it contains no odd cycles — which we can describe as a sequence of edges in the graph which starts and ends with the same edge (without counting that final edge twice). Then there are no sequence of variables $x_e, x_f, x_g, \ldots, x_e$ of odd length in $\phi$, in which adjacent variables are involved in a common clause. Then the formula $\phi$ would be bipartite in the manner described earlier.

  4. Counting the number of matchings in arbitrary bipartite graphs, in particular, can be used to count the number of perfect matchings in a bipartite graph: given an input bitrarite graph $G = (A \cup B, E)$ with two bipartitions $A, B$ of the same size $n$, one can create graphs $G_k$ by augmenting $A$ with anywhere $0 \leqslant k \leqslant n$ extra vertices connected to all of the vertices of $B$. Because all matchings in $G$ of a given size contribute differently to the number of matchings in $G_k$, by counting these one can determine the number of matchings in $G$ of size $n$ (that is, which are perfect matchings); and note that counting the number of perfect matchings in bipartite graphs is equivalent to computing permanents of $\{0,1\}$-matrices by a simple correspondance.

The class of instances of #2-SAT which are shown to be #P-hard are then the monotone bipartite instances.

Question: What are the other special cases of #2-SAT which are #P-complete, as a result of this or some other reduction?

It would be interesting if, in addition to showing/citing a reduction, people could also describe an intuitive reason for how the special case might provide obstacles to natural approaches to counting the satsifying assignments. For instance, although MONOTONE-2-SAT is trivially solvable ($\mathbf x = 1^n$ is always a solution), monotone instances are the ones in which assigning some variable to a fixed value will routinely fail to impose many constraints on the remaining variables. Fixing any variable $x_j = 0$ only restricts the values of the variables immediately related to it by some clause; and setting $x_j = 1$ doesn't restrict the possible values of any other variables at all. (It's not clear that the comparable restriction to bipartite graphs is significant in the same way, however; the bipartite restriction seems to add structure rather than removing it, but it fails to add structure enough to count efficiently.)

Edited to add. Bonus points will be awarded for any such class which doesn't ultimately rely on the existence of monotone instances (as #2-BIPARTITE-SAT does above, whose hardness is apparently due to the inclusion of the #P-hard special case #2-MONOTONE-BIPARTITE-SAT). For instance, an argument for the hardness of #2-BIPARTITE-SAT which doesn't rely on monotonic instances (but might rely on some other sub-family) would be interesting.

share|improve this question

1 Answer 1

#3-Regular Bipartite Planar Vertex Cover is #P-Complete

As counting vertex covers is exactly the same as counting satisfying assignments of a monotone #2-SAT instance, the above result implies that it is #P-complete to count satisfying assignments of a #2-SAT instance which is monotone and 3-regular and bipartite and planar.

This in turn means that, in addition to the two #2-MONOTONE-SAT and #2-BIPARTITE-SAT special cases already cited in the question, the two #2-CUBIC-SAT and #2-PLANAR-SAT special cases are #P-complete as well.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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