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
1
$\begingroup$

The problem is #P-hard, as we prove in a recent preprint: https://arxiv.org/abs/1908.07093

The way the preprint is phrased is closer to the equivalent formulation of the problem given at the end of my question: you have a bipartite graph $(X \cup Y, E)$ and you want to know how many triples $(X', Y', E')$ of subsets $X' \subseteq X$, $Y' \subseteq Y$, $E' \subseteq E$ there are such that we keep two vertices in $X'$ and $Y'$ connected by an edge in $E'$, i.e., $E' \cap (X' \times Y')$ is non-empty. This can again be equivalently reformulated in database or first-order logic terminology, which is what the preprint uses: you have a structure consisting of facts $R(a_1), \ldots, R(a_n)$, $T(b_1), \ldots, T(b_m)$, and $S(a_{i_1}, b_{j_1}), \ldots, S(a_{i_k}, b_{j_k})$ coding the bipartite graph (without multi-edges, i.e., $(a_{i_p}, b_{j_p}) \neq (a_{i_q}, b_{j_q})$ for all $p \neq q$), and you want to know how many subsets of these sets of facts satisfy the conjunctive query $\exists x \, y ~ R(x) \land S(x, y) \land T(y)$.

In the terminology of the preprint, this query is a self-join-free non-hierarchical conjunctive query (indeed, it is the simplest such example of a query, which we call $Q_1$), and hardness of this problem (the so-called model counting problem) is shown in the preprint: this is the simplest case of Theorem 4.2, with $r=1, s=1, t=1$.

$\endgroup$

Your Answer

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

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