Not-All-Equal 3SAT

Input

Set $U$ of variables, collection $C$ of clauses over $U$ such that each clause $c \in C$ has $|c| = 3$.

Question

Is there a truth assignment for $U$ such that each clause in $C$ has at least one true literal and at least one false literal?

Classes

• NP-complete

Comments

Remains NP-complete even if no $c \in C$ contains a negated literal.

Proofs

NP-complete

Transformation from 3-Satisfiability (Schaefer, 1978).

Reducible from

• 3-Satisfiability

Reducible to

• Partition into Perfect Matchings

References

• Schaefer, T. J. (1978). The complexity of satisfiability problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804350