Count satisfying assignments of CNF formulas over all possible negation assignments

Question

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.

Answer 1

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