Definition
k-Satisfiability Problem
For a fixed
, the -satisfiability problem is the decision problem of deciding whether a given CNF propositional formula in which every clause contains at most literals is satisfiable. Equivalently, the input is a formula
with
for all , and the question is whether there exists an interpretation such that It’s a special problem class of SAT.
Special Cases
- 2-SAT is the
-satisfiability problem for . - 3-SAT is the most common special case in NP-completeness proofs.