<p>The problem is #P-hard, as we prove in a recent preprint: <a href="https://arxiv.org/abs/1908.07093" rel="nofollow noreferrer">https://arxiv.org/abs/1908.07093</a></p>

<p>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 <span class="math-container">$(X \cup Y, E)$</span> and you want to know how many triples <span class="math-container">$(X', Y', E')$</span> of subsets <span class="math-container">$X' \subseteq X$</span>, <span class="math-container">$Y' \subseteq Y$</span>, <span class="math-container">$E' \subseteq E$</span> there are such that we keep two vertices in <span class="math-container">$X'$</span> and <span class="math-container">$Y'$</span> connected by an edge in <span class="math-container">$E'$</span>, i.e., <span class="math-container">$E' \cap (X' \times Y')$</span> 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 <span class="math-container">$R(a_1), \ldots, R(a_n)$</span>, <span class="math-container">$T(b_1), \ldots, T(b_m)$</span>, and <span class="math-container">$S(a_{i_1}, b_{j_1}), \ldots, S(a_{i_k}, b_{j_k})$</span> coding the bipartite graph (without multi-edges, i.e., <span class="math-container">$(a_{i_p}, b_{j_p}) \neq (a_{i_q}, b_{j_q})$</span> for all <span class="math-container">$p \neq q$</span>), and you want to know how many subsets of these sets of facts satisfy the conjunctive query <span class="math-container">$\exists x \, y ~ R(x) \land S(x, y) \land T(y)$</span>.</p>

<p>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 <span class="math-container">$Q_1$</span>), 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 <span class="math-container">$r=1, s=1, t=1$</span>. </p>

CC BY-SA 4.0
2019-08-21T10:02:35.110Z
2019-08-21T10:02:35.110Z
Antoine Amarilli 'a3nm'
<p>The #PP2DNF problem is the following: we have variables <span class="math-container">$X = \{x_1, \ldots, x_n\}$</span>, <span class="math-container">$Y = \{y_1, \ldots, y_n\}$</span>, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form <span class="math-container">$\phi = \bigvee_{1\leq i \leq l} x_{p_i} \land y_{q_i}$</span>, and we want to count its number of satisfying assignments, i.e., the number of Boolean functions from <span class="math-container">$X \cup Y$</span> such that <span class="math-container">$\phi$</span> evaluates to true under this valuation. This problem is well-known to be #P-hard by the work of <a href="https://epubs.siam.org/doi/abs/10.1137/0212053" rel="nofollow noreferrer">Provan and Ball</a> (sorry, no open-access version).</p>

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

<p><strong>Is this version of the problem also #P-hard?</strong></p>

<p>Another equivalent way to phrase the problem is in terms of bipartite graphs: we can see <span class="math-container">$\phi$</span> as a bipartite graph between <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> (each clause being an edge, and #PP2DNF asks about the number of subsets of <span class="math-container">$X \cup Y$</span> that contain some pair of vertices that are connected by an edge (i.e., how many subsets are <em>not</em> 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.</p>

CC BY-SA 4.0
2019-03-20T07:09:37.743Z
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}$?
holf
CC BY-SA 4.0
2019-03-20T08:24:03.663Z
@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.
Antoine Amarilli 'a3nm'
<cc.complexity-theory><counting-complexity>
Complexity of #PP2DNF where we also count on the number of clauses
Antoine Amarilli 'a3nm'
# Complexity of #PP2DNF where we also count on the number of clauses

(Asked by: username_0 on 2019-03-19)

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](https://epubs.siam.org/doi/abs/10.1137/0212053) (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.

**Tags:** cc.complexity-theory, counting-complexity
> **Comments:**
> **username_1**: 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}$?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_0 on 2019-08-21. Score: 2 | Accepted answer

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


---

