本节书摘来自华章计算机《计算复杂性:现代方法》一书中的第2章,第2.3节,作者 [美]桑杰夫·阿罗拉(Sanjeev Arora),博阿兹·巴拉克(Boaz Barak),译 骆吉洲,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.3 库克勒维定理:计算的局部性
1971年前后,库克(Cook)和勒维(Levin)各自独立地发现了NP完全性的概念并给出了一些NP完全的组合问题的例子,这些NP完全问题的定义看上去与图灵机似乎毫无关系。很快,卡普证明了NP完全性是广泛存在的,并且许多有实践意义的问题都是NP完全的。如今,各个分支学科中数以千计的计算问题已经被证明是NP完全的。
2.3.1 布尔公式、合取范式和SAT问题
2.3.2 库克勒维定理
2.3.3 准备工作:布尔公式的表达能力
2.3.4 引理2.11的证明
2.3.5 将SAT归约到3SAT
2.3.6 深入理解库克勒维定理
为什么是3SAT问题?
读者可能会疑惑,为什么3SAT问题的NP完全性比定理2.9中语言TMSAT的NP完全性要有意义得多呢?第一个原因是,3SAT问题在证明其他问题的NP完全性时非常有用:3SAT问题具有极其简单的组合结构,便于归约过程采用。第二个原因是,命题逻辑在数理逻辑中具有中心地位,这正是库克和勒维首先研究3SAT问题的原因所在。第三个原因是,3SAT具有重要的实践意义:实际上,3SAT问题是约束满足问题的一个简单特例,而约束满足问题广泛存在于包含人工智能在内的许多领域中。