k-CNF SAT(k-SAT)は、各節(クローズ)に最大k個のリテラルを含む連言標準形(CNF)のブール論理式について、すべての節を同時に真にする変数の割り当てが存在するかを問う決定問題である。充足可能性問題(SAT)の特殊な場合で、2-SATは多項式時間で解けるが、3-SATをはじめk≥3の場合はNP完全である。
SATは1971年にスティーヴン・クックがNP完全であることを証明した最初の問題であり、3-SATは他の問題のNP困難性を示す帰着の出発点として広く使われる。変数がn個のとき全割り当てを試すと2^n時間がかかり、2^{cn}(c<1)時間で動作するアルゴリズムが知られている。指数時間仮説(ETH)は、この問題を準指数時間で解けないとする予想である。実務ではSATソルバーがハードウェア・ソフトウェア検証や計画問題などに用いられる。