2
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ 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$. $\endgroup$ Feb 4, 2023 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.