“Insensitive” CNF/DNF SAT always satisfying same number of clauses

Question

I came across this paper, which mentions an interesting variation on SAT:

We call a CNF formula F insensitive if every total assignment α satisfies the same number of clauses of F.

I hadn't come across this before. You can easily define the same property for DNF formulae as well.

Which brings me to the following question:

Given either a DNF or CNF formula, how hard is it to tell if the formula is insensitive?

It is clear that the decision problem "is this formula insensitive?" for both DNF and CNF is in co-NP, because two assignments satisfying different numbers of clauses serve as a "no" certificate. Its complement, which is "is this formula sensitive?" is in NP. But are these problems complete in their respective classes?

I suspect the answer is "yes," because most variants of SAT turn out to be NP-complete. But I don't know how to prove this, and I cannot find any information on "insensitive" formulas outside of this paper. Does any info on this exist?

Answer 1

Consider a DNF $C_1 \lor \cdots \lor C_m$.

For any clause $C_i$, we can compute the probability that a random assignment satisfies $C_i$: it is 0 if $C_i$ contains both a variable and its negation, and otherwise it is $2^{-|C_i|}$, where $|C_i|$ is the number of literals in $C_i$.

For any two clauses $C_i,C_j$, we can compute the probability that a random assignment satisfies both $C_i$ and $C_j$: it is just the probability that a random assignment satisfies $C_i \land C_j$.

Given this data, it is routine to compute the variance of the number of satisfied clauses under a random assignment. The DNF is insensitive iff the variance is zero. The corresponding algorithm runs in polynomial time, and so the problem is in $\mathsf{P}$.

If we have a CNF, we can negate it to obtain a DNF which is insensitive iff the original CNF is.