Is deciding whether all satisfying assignments are NAE assignments coNP-complete?

Question

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.

Answer 1

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.