布尔可满足性问题（Boolean satisfiability problem, SAT）

SAT 问题属于决定性问题，也是第一个被证明属于NP完全的问题，1970年 Cook 证明 SAT 问题是NP-完全问题。即Cook定理。Cook说明若SAT多项式时间可解，则所有NP问题多项式时间可解。

Cook定理证明 SAT 问题属于 NPC 问题的核心步骤：

  1. 证明 SAT 问题属于 NP 问题，这明显成立（给定一个真值指派，按顺序求解即可）
  2. 证明其他所有属于 NP 类的判定问题都可以通过某多项式变换变换为 SAT 问题

SAT 问题

实例

布尔变量集合

U={u1,u2,⋯ ,un},U=\left\{u_{1}, u_{2}, \cdots, u_{n}\right\},

项集合（也就是多个布尔变量或其取反后的布尔变量构成的集合）

C={C1,C2,⋯ ,Cm},C=\left\{C_{1}, C_{2}, \cdots, C_{m}\right\},

其中

Ci={u[i,1],⋯ ,u[i,ki]}⊆U∪U⃗,Uˉ={uˉ1,⋯ ,uˉn}C_{i}=\left\{u[i, 1], \cdots, u\left[i, k_{i}\right]\right\} \subseteq U \cup \vec{U}, \quad \bar{U}=\left\{\bar{u}_{1}, \cdots, \bar{u}_{n}\right\}

询问 是否存在 UU 的真值指派: U→{F,T},U \rightarrow\{\mathrm{F}, \mathrm{T}\}, 满足

⋀i=1m(∑j=1kiu[i,j])=T\bigwedge_{i=1}^{m}\left(\sum_{j=1}^{k_{i}} u[i, j]\right)=\mathrm{T}

证明方法简述

这里需要回顾一下 NTM, 之前在介绍 NP 问题时说过，NTM 实际上就是假想出来用来在多项式时间内求 NP 问题的机器。在解一个非判定问题时候，将所有问题的解的可能穷举出来，最后再对其逐一进行多项式判定，从而可以在多项式时间内解答 NP 问题。

而库克定理将 NTM 执行 NP 问题的验证过程进行了抽象。

将 NTM 中的每个状态都用一个布尔变量表示，随后将验证程序执行过程中应该受到的约束条件表达为合取范式。布尔变量+合取范式，这就构成了一个 SAT 问题，也即任意的 NP 问题都被多项式变换为了 SAT 问题。而这完全符合了 NPC 问题的定义：

如果有一个终极的 NP 问题，其他所有的 NP 问题都可以归约到这个问题上，那么当这一个终极 NP 问题解决时，所有的 NP 问题就都解决了。

如果这个终极的问题存在，那么这个终极问题就被称为是 NPC，能归约到该问题上的其他问题被称为NPC类问题。

具体的证明过程限于时间，暂且不表。