3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Wow, deafening silence on this question. I don't have an answer but my intuition (maybe wrongly) tells me that insensitivity isn't NP-hard to decide. The problem feels like graph isomorphism in that almost all instances are trivially easy to decide and the problem only gets hard when there are lots of symmetries present in the instance. $\endgroup$ – Kyle Jones Jul 8 '17 at 5:22
1
$\begingroup$

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.

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