<p>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):</p>

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

<p>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$.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2017-07-10T10:58:37.100Z
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$.
TheoryQuest1
CC BY-SA 3.0
2017-07-10T20:03:56.647Z
OK, I'll edit it later when I'm more free.
Mikhail Rudoy
CC BY-SA 3.0
2017-07-10T06:31:42.340Z
2017-07-11T19:05:58.537Z
2017-07-11T19:05:58.537Z
Mikhail Rudoy
<p>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)$. </p>

<p>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 &gt; 2$?</p>

<p>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.</p>

CC BY-SA 3.0
2017-07-10T05:20:06.490Z
** This is a must simplified version of a previous question I posted (and now deleted) because it might have been somewhat confusing.
TheoryQuest1
<cc.complexity-theory><np-hardness><sat><np-complete>
Is deciding whether all satisfying assignments are NAE assignments coNP-complete?
TheoryQuest1
# Is deciding whether all satisfying assignments are NAE assignments coNP-complete?

(Asked by: username_0 on 2017-07-10)

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.

**Tags:** cc.complexity-theory, np-hardness, sat, np-complete

> **Comments:**
> **username_0**: ** This is a must simplified version of a previous question I posted (and now deleted) because it might have been somewhat confusing.  

---

## 1 answers

### Answer by username_1 on 2017-07-10. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$.  
> **username_1**: OK, I'll edit it later when I'm more free.  

---

