3
$\begingroup$

The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \bigvee_{1\leq i \leq l} x_{p_i} \land y_{q_i}$, and we want to count its number of satisfying assignments, i.e., the number of Boolean functions from $X \cup Y$ such that $\phi$ evaluates to true under this valuation. This problem is well-known to be #P-hard by the work of Provan and Ball (sorry, no open-access version).

I'm interested in a variant of the problem where we also want to count on the clauses. Specifically, seeing $\phi$ as a set of clauses, I want to count the number of pairs $(\phi', \nu)$ of a subset of the clauses $\phi' \subseteq \phi$ and of a valuation $\nu$ of $X \cup Y$ such that $\phi'$ evaluates to true under $\nu$. For instance, if $\phi$ has two clauses, i.e., $\phi = C_1 \lor C_2$, I will count the number of satisfying valuations of $\phi$, plus the number of satisfying valuations of $C_1$, plus the number of satisfying valuations of $C_2$, plus 0 (the empty disjunction is always false). Equivalently I want to compute $2 n_1 + 2 n_2 + 3 n_{12}$ where $n_1$ is the number of valuations satisfying $C_1$ but not $C_2$, $n_2$ is the number of valuations satisfying $C_2$ but not $C_1$, and $n_{12}$ is the number of valuations satisfying both.

Is this version of the problem also #P-hard?

Another equivalent way to phrase the problem is in terms of bipartite graphs: we can see $\phi$ as a bipartite graph between $X$ and $Y$ (each clause being an edge, and #PP2DNF asks about the number of subsets of $X \cup Y$ that contain some pair of vertices that are connected by an edge (i.e., how many subsets are not independent sets). My version of the problem asks how many subsets of the vertex and edge sets there are such that we kept two vertices and an edge between these two vertices.

$\endgroup$
  • $\begingroup$ Am I right to say that it is a form of model counting where the weight of a satisfying assignment is the number of subset of "clauses" (terms would be better suited for DNF btw) it satisfies? So if the DNF has $m$ clauses and $\tau$ is a satisfying assignment satisfying $k$ clauses, its weight is $(2^k-1) \times 2^{m-k}$? $\endgroup$ – holf Mar 20 at 7:09
  • $\begingroup$ @holf: If there are $m$ clauses and you satisfy $k$ then the weight of the assignment is the number of satisfied subsets, which is $2^k-1$ (choosing a non-empty subset of the satisfied clauses), times $2^{m-k}$ (choosing any subset of the other clauses), as you say. $\endgroup$ – a3nm Mar 20 at 8:24

Your Answer

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

Browse other questions tagged or ask your own question.