3-Satisfiability

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 satisfying truth assignment for $C$?

Classes

• NP-complete

Comments

Remains NP-complete even if each clause contains either only negated variables or only un-negated variables ([problem:monotone-3sat]) (Gold, 1978), or if for each $u \in U$ there are at most 5 clauses in $C$ that contain either $u$ or $\overline{u}$. Also remains NP-complete for expressions in which each variable is restricted to appear at most three times, and each literal at most twice. NP-hard if all but one variable occur exactly three times.

Proofs

NP-complete

Transformation from Satisfiability (Cook, 1971).

Reducible from

• Satisfiability

Reducible to

• 3-Dimensional Matching
• Domatic Number
• Graph K-Colorability
• Induced Path
• Maximum 2-Satisfiability
• Monochromatic Triangle
• Not-All-Equal 3SAT
• One-in-Three 3SAT
• Vertex Cover

References

• Gold, E. M. (1978). Complexity of automaton identification from given data. Information and Control, 37(3), 302–320. https://doi.org/10.1016/s0019-9958(78)90562-4
• Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing - STOC ’71. https://doi.org/10.1145/800157.805047