# Is checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?

I want to know if checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?

By 3-literal clause, I mean it can have a clause can have at most 3 literals.

I think this problem is NP-complete or co-np complete as it seems like a complement of 3-NAE-SAT?

I want to know if its NP-complete and if it is then does there exist a reduction from 3-NAE-SAT to this variant of SAT which we may call 3-All-Equal-SAT?

## 1 Answer

The problem can be solved in polynomial time. Construct a new formula as follows:

• The set of variables of the new formula is the set of variables of the original instance plus one variable $$x_c$$ for each clause $$c$$. The idea is that all literals in $$c$$ will be forced to have the same value of $$x_c$$.

• For each clause $$(\ell_1, \ell_2, \ell_3)$$ of the original instance, and for each $$i \in \{1,2,3\}$$, create the following clauses: $$(x_c \implies\ell_i) \wedge (\overline{x}_c \implies \overline{\ell_i})$$, which can be equivalently written as $$(\overline{x_c} \vee \ell_i) \wedge (x_c \vee \overline{\ell_i})$$.

Notice that the resulting formula is an instance of 2-SAT, which can be solved using standard algorithms.

• Clever. It seems we can do without the extra clause-variables using three new clauses for each $(\ell_1, \ell_2, \ell_3)$: $\ell_1\Rightarrow \ell_2$, $\ell_2\Rightarrow \ell_3$, and $\ell_3\Rightarrow \ell_1$. Feb 4, 2023 at 0:51