<p>The quantity <span class="math-container">$\sum_k|\phi_k|$</span> can be computed in polynomial time, in fact, in uniform <span class="math-container">$\mathrm{TC}^0$</span>. By double counting, we have
<span class="math-container">$$\sum_k|\phi_k|=|\{(a,k):a\models\phi_k\}|=\sum_{a\in\{0,1\}^n}|\{k:a\models\phi_k\}|.$$</span>
Now, if <span class="math-container">$a\in\{0,1\}^n$</span> is any assignment, and <span class="math-container">$C$</span> a clause in <span class="math-container">$l$</span> literals, then there are exactly <span class="math-container">$2^l-1$</span> ways how to negate the literals in <span class="math-container">$C$</span> so that it is satisfied by <span class="math-container">$a$</span>: the unique unsatisfied instance is the one where every literal is negated or not opposite to what <span class="math-container">$a$</span> says. Moreover, for a CNF <span class="math-container">$C_1\land\dots\land C_m$</span>, we choose the negations of literals of each clause <span class="math-container">$C_j$</span> independently, and the whole formula is satisfied iff each <span class="math-container">$C_j$</span> is satisfied, hence irrespective of <span class="math-container">$a$</span> and of the structure of the formula,
<span class="math-container">$$|\{k:a\models\phi_k\}|=\prod_{j=1}^m(2^{l_j}-1),$$</span>
hence
<span class="math-container">$$\sum_k|\phi_k|=2^n\prod_{j=1}^m(2^{l_j}-1).$$</span></p>

CC BY-SA 4.0
2019-06-17T13:46:22.303Z
2019-06-17T13:46:22.303Z
Emil Jeřábek
<p>Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the <em>sum</em> of the counts of satisfying assignments for the set?</p>

<p>More formally, consider a CNF formula over a boolean variable set <span class="math-container">$V$</span> described by <span class="math-container">$\phi = C_1 \wedge C_2 \wedge \dots \wedge C_m $</span>, where each clause <span class="math-container">$C_j$</span> is a disjunction over a subset of <span class="math-container">$V$</span>, and let <span class="math-container">$|\phi|$</span> denote the count of the satisfying assignments of <span class="math-container">$\phi$</span>. Let <span class="math-container">$l_j$</span> denote the length of <span class="math-container">$C_j$</span>. From each <span class="math-container">$C_j$</span> one can create <span class="math-container">$2^{l_j}-1$</span> other clauses by negating one or more of the literals that appear in it. One can therefore generate formulas <span class="math-container">$\phi_k$</span> where <span class="math-container">$k=1,\dots,2^{\sum_jl_j}$</span> with the same "structure" (i.e., the same factor graph topology) as <span class="math-container">$\phi$</span>. How hard is it to compute <span class="math-container">$\sum_k |\phi_k|$</span>?</p>

<p>Naively, one might expect that this should be as hard as counting the satisfying assignments of the hardest instance in the set. Is this correct? Or are there any interesting special cases where this intuition may be wrong? What about the restricted problem of getting the total count modulo some integer greater than 1? Does this problem have a name?</p>

<p>For example, if <span class="math-container">$\phi$</span> is a 3SAT formula, I would expect the problem to be #P-hard. On the other hand, if <span class="math-container">$\phi$</span> is an XORSAT formula, each <span class="math-container">$|\phi_k|$</span> is easy to evaluate, but there is an exponentially large number of them.</p>

CC BY-SA 4.0
2019-06-11T08:21:03.430Z
Could you be a bit more formal? I do not understand what you mean by "adding negations to a single monotone CNF".
holf
CC BY-SA 4.0
2019-06-11T19:53:24.073Z
Question edited to hopefully make it clearer.
delete000
CC BY-SA 4.0
2019-06-11T21:37:59.627Z
Summing the number of satisfying assignments over all negation instances is the same as summing the number of negation instances satisfied by a given assignment over all assignments. This is easy: irrespective of the structure of the formula, the answer is $2^n\prod_j(2^{l_j}-1)$.
Emil Jeřábek
CC BY-SA 4.0
2019-06-14T13:11:04.497Z
@EmilJeřábek Please convert your comment into answer.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-06-14T14:33:09.803Z
@EmilJeřábek could you also perhaps comment on the complexity of *partial* counts that take into account only a subset of the variables (as in e.g. existential second-order formulas $\Sigma_1^1$)
delete000
CC BY-SA 4.0
2019-06-17T13:47:39.820Z
@delete000 I’m not quite sure what you mean.
Emil Jeřábek
<cc.complexity-theory><approximation-algorithms><sat><counting-complexity>
Count satisfying assignments of CNF formulas over all possible negation assignments
delete000
# Count satisfying assignments of CNF formulas over all possible negation assignments

(Asked by: username_0 on 2019-06-07)

Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the *sum* of the counts of satisfying assignments for the set?

More formally, consider a CNF formula over a boolean variable set $V$ described by $\phi = C\_1 \wedge C\_2 \wedge \dots \wedge C\_m $, where each clause $C\_j$ is a disjunction over a subset of $V$, and let $|\phi|$ denote the count of the satisfying assignments of $\phi$. Let $l\_j$ denote the length of $C\_j$. From each $C\_j$ one can create $2^{l\_j}-1$ other clauses by negating one or more of the literals that appear in it. One can therefore generate formulas $\phi\_k$ where $k=1,\dots,2^{\sum\_jl\_j}$ with the same "structure" (i.e., the same factor graph topology) as $\phi$. How hard is it to compute $\sum\_k |\phi\_k|$?

Naively, one might expect that this should be as hard as counting the satisfying assignments of the hardest instance in the set. Is this correct? Or are there any interesting special cases where this intuition may be wrong? What about the restricted problem of getting the total count modulo some integer greater than 1? Does this problem have a name?

For example, if $\phi$ is a 3SAT formula, I would expect the problem to be #P-hard. On the other hand, if $\phi$ is an XORSAT formula, each $|\phi\_k|$ is easy to evaluate, but there is an exponentially large number of them.

**Tags:** cc.complexity-theory, approximation-algorithms, sat, counting-complexity

> **Comments:**
> **username_1**: Could you be a bit more formal? I do not understand what you mean by "adding negations to a single monotone CNF".  
> **username_0**: Question edited to hopefully make it clearer.  
> **username_2**: Summing the number of satisfying assignments over all negation instances is the same as summing the number of negation instances satisfied by a given assignment over all assignments. This is easy: irrespective of the structure of the formula, the answer is $2^n\prod_j(2^{l_j}-1)$.  
> **username_3**: @EmilJeřábek Please convert your comment into answer.  
> **username_0**: @EmilJeřábek could you also perhaps comment on the complexity of *partial* counts that take into account only a subset of the variables (as in e.g. existential second-order formulas $\Sigma_1^1$)  
> **username_2**: @username_0 I’m not quite sure what you mean.  

---

## 1 answers

### Answer by username_2 on 2019-06-17. Score: 6 | Accepted answer

The quantity $\sum\_k|\phi\_k|$ can be computed in polynomial time, in fact, in uniform $\mathrm{TC}^0$. By double counting, we have
$$\sum\_k|\phi\_k|=|\{(a,k):a\models\phi\_k\}|=\sum\_{a\in\{0,1\}^n}|\{k:a\models\phi\_k\}|.$$
Now, if $a\in\{0,1\}^n$ is any assignment, and $C$ a clause in $l$ literals, then there are exactly $2^l-1$ ways how to negate the literals in $C$ so that it is satisfied by $a$: the unique unsatisfied instance is the one where every literal is negated or not opposite to what $a$ says. Moreover, for a CNF $C\_1\land\dots\land C\_m$, we choose the negations of literals of each clause $C\_j$ independently, and the whole formula is satisfied iff each $C\_j$ is satisfied, hence irrespective of $a$ and of the structure of the formula,
$$|\{k:a\models\phi\_k\}|=\prod\_{j=1}^m(2^{l\_j}-1),$$
hence
$$\sum\_k|\phi\_k|=2^n\prod\_{j=1}^m(2^{l\_j}-1).$$


---

