k-CNF SAT(k-SAT)是这样一个决策问题:给定一个合取范式(CNF)布尔公式,其中每个子句最多包含k个文字,判断是否存在一组变量赋值使所有子句同时为真。它是布尔可满足性问题(SAT)的特例:2-SAT可在多项式时间内求解,而3-SAT以及所有k≥3的k-SAT都是NP完全问题。
SAT是1971年由斯蒂芬·库克证明的第一个NP完全问题,3-SAT则是证明其他问题NP困难性时常用的归约起点。当变量为n个时,枚举所有赋值需要2^n时间,目前已知有运行时间为2^{cn}(c<1)的算法。指数时间假设(ETH)猜想该问题无法在亚指数时间内求解。在实践中,SAT求解器被用于硬件与软件验证、规划等任务。