1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you be a bit more formal? I do not understand what you mean by "adding negations to a single monotone CNF". $\endgroup$ – holf Jun 11 at 8:21
  • $\begingroup$ Question edited to hopefully make it clearer. $\endgroup$ – delete000 Jun 11 at 19:53
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Emil Jeřábek supports Monica Jun 11 at 21:37
  • 1
    $\begingroup$ @EmilJeřábek Please convert your comment into answer. $\endgroup$ – Mohammad Al-Turkistany Jun 14 at 13:11
  • $\begingroup$ @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$) $\endgroup$ – delete000 Jun 14 at 14:33
6
$\begingroup$

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

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