Let the language $L$ consist of the $k$-CNF formulas $\phi$ with the property that any satisfying assignment $x$ of $\phi$ is a Not-All-Equal (NAE) assignment, i.e. every clause of $\phi$ has at least one false literal under $x$. Equivalently, $L$ includes those $k$-CNF formulas $\phi$ for which $\phi(x) \implies \phi(\neg x)$.

Clearly $L$ is in coNP, since a certificate for a "no" instance is given by a satisfying assignment which is not a NAE assignment. Is $L$ also coNP-complete for $k > 2$?

As a simple example consider the $2$-CNF formula $(a \vee b) \wedge (\neg a \vee \neg b)$ whose satisfying solutions have exactly one of $a$ or $b$ true, but not both.

  • $\begingroup$ ** This is a must simplified version of a previous question I posted (and now deleted) because it might have been somewhat confusing. $\endgroup$ – TheoryQuest1 Jul 10 '17 at 5:20

Consider the following reduction from coNP-complete problem $k$-UNSAT to your language $L$ (where $k$-UNSAT is the language of all unsatisfiable $k$-CNF formulas):

On input a $k$-CNF formula $\psi$, create new variables $x_1, \ldots, x_k$ and output formula $\phi = \psi \land (x_1 \lor x_2 \lor \cdots \lor x_k)$.

If $\psi$ is unsatisfiable then $\phi$ is also unsatisfiable. In that case, it is vacuously true that every satisfying assignment $x$ of $\phi$ is a NAE assignment. (Equivalently, $\phi(x) \implies \phi(\neg x)$ is always true since $\phi(x)$ is always false.) This shows that $\phi \in L$. Thus, we see that if $\psi \in k$-UNSAT (that is, $\psi$ is unsatisfiable) then $\phi \in L$.

On the other hand, if $\psi$ is satisfiable then $\phi$ is also satisfiable by keeping the old assignment for the variables in $\psi$ and setting $x_1 = x_2 = \ldots = x_k = 1$. Notice that this is a satisfying assignment of $\phi$ that is not NAE. In other words, $\phi \not\in L$. Thus, we see that if $\psi \not\in k$-UNSAT (that is, $\psi$ is satisfiable) then $\phi \not\in L$.

The above shows that $\psi \in k$-UNSAT if and only if $\phi \in L$ and therefore that the reduction is correct. Since $k$-UNSAT is coNP-complete, we can conclude that $L$ is coNP-hard.

  • $\begingroup$ That is an elegant reduction. Thanks. But, I think to make it less confusing $\phi$ and $\psi$ should be interchanged as the original problem is mentioned as $\phi$. $\endgroup$ – TheoryQuest1 Jul 10 '17 at 10:58
  • $\begingroup$ OK, I'll edit it later when I'm more free. $\endgroup$ – Mikhail Rudoy Jul 10 '17 at 20:03

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.