k-Satisfiability Problem

computation logic sat

Definition

k-Satisfiability Problem

For a fixed $k\ge 1$, the $k$-satisfiability problem is the decision problem of deciding whether a given CNF propositional formula in which every clause contains at most $k$ literals is satisfiable.

Equivalently, the input is a formula

$$\Phi =C_1\wedge \cdots \wedge C_m$$

with $|C_i|\le k$ for all $i$, and the question is whether there exists an interpretation $I$ such that

$$I\models \Phi .$$

It’s a special problem class of SAT.

Special Cases

• 2-SAT is the $k$-satisfiability problem for $k=2$.
• 3-SAT is the most common special case in NP-completeness proofs.