形式语言课件：第7章 NP完全性

第7章NP完全性7.1多项式时间规约7.2P类/NP类问题7.3其他NP完全问题第7章NP完全性7．1多项式时间规约定义7.1.1如果存在计算函数f:Σ*->Σ*的多项式界限的Turing机M，那么f称为多项式时间可计算的。现在设L1,L2⊆Σ*是语言，设:Σ*->Σ*是多项式时间可计算的函数。如果对每个x∈Σ*下列关系成立：

x∈L1当且仅当(x)∈L2,那么称为从L1到L2的多项式归约。

注意：对比定义5.4.1和定理5.4.1，前者定义归约，后者为多项式归约。P类问题与NP类问题的定义P＝{L|L是一个能在多项式时间内被一台DTM所接受的语言}NP＝{L|L是一个能在多项式时间内被一台NDTM所接受的语言}例7.1.1构造一个从Hamilton圈到可满足性的多项式时间归约。主要从Hamilton问题出发，按照要求构造一系列子句，满足这些子句就满足Hamilton解，而且这些子句的构造和判别都是可以在多项式时间完成。再比如：三个问题(划分、背包、双机调度)，可证明存在六个多项式归约，使得任意一个问题都可以归约到另外一个问题上！引理7.1.1

如果t1是从L1到L2的多项式归约并且t2是从L2到L3的多项式归约，那么它们的合成t1

。t2就是从L1到L3的多项式归约。(传递性)定义7.1.2

设L⊆Σ*是语言，如果（a）L∈NP；并且 （b）对每一个语言L’∈NP，存在L’到L的多项式归约，那么L称为是NP完全的。任何NP完全语言是否属于P的问题等价于整个P＝NP问题。定理7.1.1

设L是NP完全语言。那么P＝NP当且仅当L∈P。证明：根据定义7.1.2和引理7.1.1，容易得出结论。7.2Cook定理(P类与NP类问题)有界铺砖：铺砖问题限定在sXs的正方形区域，是否存在满足铺砖条件的铺砖系统？定理7.2.1

有界铺砖是NP完全的。证明：首先证明它属于NP；最后证明NP里所有语言都可归约到有界铺砖上。略定理7.2.2(Cook定理)：可满足性是NP完全的。证明：前面已经论证过“可满足性”属于NP，进一步构造把有界铺砖归约到可满足性上。略定理7.2.3

三元可满足性是NP完全的。证明：它是“可满足性”的特殊情形，所以它是属于NP；接着构造把“可满足性”规约到三元可满足性上。略最大可满足性：给定子句集F和整数K，是否存在满足至少K各子句的真值赋值？定理7.2.4

最大可满足性是NP完全的。(证明类似三元)7.3其它的NP完全问题对于任一新的判定问题II，其NP完全性的论证过程应由以下四个部分组成：1）证明IINP；2）选取一个已知为NP完全的问题II’；3）构造一个从II’到II的变换f；4）证明f为一个多项式时间变换。7.3部分NP完全问题树恰当覆盖：给定有穷集D，以及m个U的子集合的族F，是否存在恰当覆盖？即F中不相交的子集构成子族L，并且U是L的并集。定理7.3.1

恰当覆盖是NP完全的。证明：首先证明它属于NP；接着构造把“可满足性”归约到恰当覆盖上。略定理7.3.2：Hamilton圈是NP完全的。证明：已经论证过Hamilton属于NP，进一步构造把恰当覆盖归约到Hamilton圈上。略定理7.3.3

无向Hamilton圈是NP完全的。证明：把普通的Hamilton圈归约到它上。略定理7.3.4

旅行商问题是NP完全的。

证明：已知它属于NP，把无向Hamilton圈归约到它上。略定理7.3.5

背包问题是NP完全的。

证明：它属于NP，把恰当覆盖归约到它上。略定理7.3.6

独立集问题是NP完全的。

证明：它属于NP，把三元可满足性归约到它上。略定理7.3.7

团和顶点覆盖都是NP完全的。7.4对付NP完全性NP完全优化问题：可用保证接近最优的解的算法。

|opt(x)-A(x)／opt(x)≤e

其中：A(x)是多项式算法，称为e近似算法。分三类（相对解的误差e来讲）a)