21
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Not exactly what you asked for at the end of your question, but there is a reduction that, given an arbitrary CNF formula $\Phi$, returns a 2-SAT formula $\Psi$ which is not monotone and which has the following property: the number of solutions of $\Psi$ having an odd number of variables set to true minus the number of solutions of $\Psi$ having an even number of variables set to true is equal to the number of solutions of $\Phi$. $\endgroup$ Feb 5, 2016 at 21:45
  • $\begingroup$ I forgot to say that $\Psi$ is also bipartite. $\endgroup$ Feb 13, 2016 at 8:21

2 Answers 2

16
$\begingroup$

#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.

$\endgroup$
7
$\begingroup$

Despite being 11 years late I hope I can still claim the bonus points! There is an (IMHO) simple and direct reduction from #SAT to #BIPARTITE-2SAT that does not rely on monotone instances. This appears in arXiv:2304.02524 by myself, Konstantinos Meichanetzidis, and John van de Wetering.

Given $r \in \mathbb{N}$ and $f : \mathbb{B}^n \to \mathbb{B}$ a CNF formula with $n$ variables and $m$ clauses, there is a bipartite 2-CNF $f'$ with $O(n + mr)$ variables such that $$|\{x \in \mathbb{B}^n \mid f(x) = 1\}| \equiv |\{x \in \mathbb{B}^n \mid f'(x) = 1\}| \pmod{2^r + 1}$$ Now suppose we have an oracle for #BIPARTITE-2SAT. Then since $|\{x \in \mathbb{B}^n \mid f(x) = 1\}| < 2^n + 1$, if we set $r = n$ then we can recover this value exactly from $|\{x \in \mathbb{B}^n \mid f'(x) = 1\}|$, which we can compute using the oracle. This gives a reduction from #SAT to #BIPARTITE-2SAT.

We can construct $f'$ from $f$ as follows:

  1. For each variable $x_i$ of $f$, add a variable $x_i'$ to $f'$
  2. For each clause $C_j$ of $f$, add a variable $y_j'$ to $f'$
  3. For each $y_j'$ add variables $z'_{j1}, z'_{j2}, \dots, z'_{jr}$ and clauses $(y_j' \lor \lnot z'_{j1}) \land (y_j' \lor \lnot z'_{j2}) \land \cdots \land (y_j' \lor \lnot z'_{jr})$ to $f'$,
  4. For every $i$ and $j$:
    • If $x_i$ occurs in $C_j$, add $\lnot x'_i \lor \lnot y'_j$ to $f'$
    • If $\lnot x_i$ occurs in $C_j$ add $x'_i \lor \lnot y'_j$ to $f'$

Clearly $f'$ is bipartite because it can be partitioned as $\{x'_i\} \cup \{z'_{jl}\}$ and $\{y'_j\}$.

This generalizes the reduction given by Giorgio Camerani in this answer about $\oplus$2SAT (they are the same when $r = 0$).

As to why this works.. in the paper (see Lemma 3 for details), we show this using the ZH calculus, which is a formal system of diagrammatic reasoning about tensor networks. In this framework, the derivation of this construction is: graphical proof for the construction of f' Here, the yellow boxes with zeros are negated clauses, white dots are variables, and grey dots are negations. I'd encourage anyone interested to have a look at the ZH calculus! (of course, the OP was an author of the predecessor to this paper, so knows all about this..)

I prefer the graphical presentation, but it is also possible to given an explanation in words: the intuition for why this works is that the subformula $f''$ of $f'$ generated by only the $x'_i$s and $y'_j$s is essentially a weighted CNF - for every satisfying assignment of $f''$, if any $y'_j$ is assigned true then there are $2^r$ ways to assign the $z'_{jl}$s to make $f'$ true, and if $y'_j$ is false then there is only one way to assign the $z'_{jl}$s. Thus we can treat $f''$ as a weighted CNF where the $y'_j$s are given weight $2^r$. However, $2^r \equiv -1 \mod 2^r + 1$, so we can think of these as having weight $-1$.

If $y'_j$ is false, then no further restrictions are imposed on the $x'_i$s. This is as if $C_j$ did not exist. If $y'_j$ is true then we assert that the $x'_i$s must appear with opposite polarity than they do in $C_j$. But this is exactly the condition for $C_j$ to be unsatisfied! Since $y'_j$ has weight $-1$, the total number of solutions of $f''$ is the number of solutions where $y'_j$ is false (and $C_j$ does not exist), minus the number of solutions $y'_j$ is true (and $C_j$ is unsatisfied). Therefore it is exactly the number of solutions where $C_j$ is satisfied! This applies to every $j$, so that the total number of solutions of $f'$ (mod $2^r + 1$) is the same as $f$.

I suppose the moral of the story here is that counting is probably hard when the structure of the formulae is not sufficiently constrained to prevent you from putting weights on variables. If you can do that, then you can maybe reconstruct other structure, including arbitrarily large clauses. It seems that the bipartite structure in this case is not intrinsic to the argument but instead an artifact of the fact that the incidence graph of a #SAT instance is naturally bipartite.

For example, in the paper, we also used this weight-and-modulo trick to reduce from #SAT to #MONOTONE-2SAT (modulus $2^r$), #2SAT with degree at most three (Fibonacci number modulus), #PERFECT-MATCHINGS (modulus $2^r + 1$). And even if you can't show that counting for a particular structure of formula is #P-hard in this way, it might be sufficient to show modulo an integer to obtain at least NP-hardness. For example, if you set $r = 0$ in the reduction above, you get a reduction from $\oplus$SAT to $\oplus$2SAT, showing that #2SAT is at least NP-hard (under randomized reductions) by the Valiant-Vazirani theorem.

$\endgroup$
9
  • $\begingroup$ Your item 4 in the construction of $f'$ is weird, it will always propagate the fact that $y'_j = 0$. Did you mean $\vee$ instead of $\wedge$? $\endgroup$
    – holf
    Apr 14, 2023 at 15:57
  • $\begingroup$ @holf ah yes I did, fixed. Thanks! $\endgroup$ Apr 14, 2023 at 18:23
  • $\begingroup$ how does this not solve SAT? You get O(n+mn) 2-SAT with 0 solutions iff SAT has 0 solutions $\endgroup$ Apr 17, 2023 at 19:25
  • 1
    $\begingroup$ No, $f$ may be unsat and $f'$ has $k(2^r+1)$ solutions for some $k$ hence $\#f = 0 = k(2^r+1) \mathsf{~mod~} (2^r+1) = \#f'$. This is actually a very elegant reduction! $\endgroup$
    – holf
    Apr 18, 2023 at 5:07
  • $\begingroup$ @TuomasLaakkonen If I take your $f'$ construction and ignore Step 3, what I get is exactly the same as mentioned in the first half of my answer cstheory.stackexchange.com/a/48282/947, which is precisely what I was referring to in my above comment to this question. $\endgroup$ May 27, 2023 at 8:56

Your Answer

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

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