Satisfiability

Input

Set $U$ of variables, collection $C$ of clauses over $U$.

Question

Is there a satisfying truth assignment for $C$?

Classes

• NP-complete

Comments

Remains NP-complete even if each $c \in C$ satisfies $|c| = 3$ (3-Satisfiability), or if each $c \in C$ satisfies $|c| \leq 3$ and, for each $u \in U$, there are at most 3 clauses in $C$ that contain either $u$ or $\overline{u}$. Also remains NP-complete if each $c \in C$ has $|c| \leq 3$ and the bipartite graph $G = (V,E)$, where $V = U \cup C$ and $E$ contains exactly those pairs $(u,c)$ such that either $u$ or $\overline{u}$ belongs to the clause $c$, is planar ([problem:planar-3sat]) (Lichtenstein, 1982). The general problem is solvable in polynomial time if each $c \in C$ has $|c| \leq 2$ (e.g. see (Even et al., 1976)).

Reducible to

• 3-Satisfiability

References

• Lichtenstein, D. (1982). Planar Formulae and Their Uses. SIAM Journal on Computing, 11(2), 329–343. https://doi.org/10.1137/0211025
• Even, S., Itai, A., & Shamir, A. (1976). On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, 5(4), 691–703. https://doi.org/10.1137/0205048