《形式语言与自动机理论：第7章 NP完全性》由会员分享，可在线阅读，更多相关《形式语言与自动机理论：第7章 NP完全性（9页珍藏版）》请在金锄头文库上搜索。
1、第7章 NP完全性 7.1 多项式时间规约多项式时间规约7.2 P类类/NP类问题类问题7.3 其他其他NP完全问题完全问题第7章 NP完全性 71 多项式时间规约定义定义7.1.1 如果存在计算函数如果存在计算函数f:*-*的多项式界限的的多项式界限的Turing机机M，那么，那么f称为称为多项式时间可计算的多项式时间可计算的。 现在设现在设L1,L2*是语言，设是语言，设 :*-*是多项式时间可计算的是多项式时间可计算的函数。如果对每个函数。如果对每个x*下列关系成立：下列关系成立： xL1 当且仅当当且仅当 (x)L2,那么那么 称为称为从从L1到到L2的多项式归约的多项式归约。 注意：
2、对比定义注意：对比定义5.4.1和定理和定理5.4.1，前者定义归约，后者为多项式归约。，前者定义归约，后者为多项式归约。P类问题与类问题与NP类问题的定义类问题的定义PL|L是一个能在多项式时间内被一台是一个能在多项式时间内被一台DTM所接受的语言所接受的语言NPL|L是一个能在多项式时间内被一台是一个能在多项式时间内被一台NDTM所接受的语言所接受的语言例例7.1.1 构造一个从构造一个从Hamilton圈到可满足性的多项式时间归约。圈到可满足性的多项式时间归约。 主要从主要从Hamilton问题出发，按照要求构造一系列子句，满足这些子句就满足问题出发，按照要求构造一系列子句，满足这些子句
3、就满足Hamilton解，而且这些子句的构造和判别都是可以在解，而且这些子句的构造和判别都是可以在多项式时间多项式时间完成。完成。再比如：三个问题再比如：三个问题(划分、背包、双机调度划分、背包、双机调度)，可证明，可证明存在六个多项式归约存在六个多项式归约，使得，使得任意一个问题都可以归约到另外一个问题上！任意一个问题都可以归约到另外一个问题上！引理引理7.1.1 如果如果t t1 1 是从是从L1 1到到L2 2的多项式归约并且的多项式归约并且t t2 2是从是从L2 2到到L3 3的多项式的多项式归约，那么它们的合成归约，那么它们的合成t t1 1 。 t t2 2就是从就是从L1到到L
4、3 3的多项式归约。的多项式归约。(传递性传递性)定义定义7.1.2 设设L*是语言，如果是语言，如果 （a）LNP；并且；并且 （b）对每一个语言）对每一个语言LNP ，存在，存在L 到到L的多项式归约，的多项式归约， 那么那么L称为是称为是NP完全的完全的。任何任何NP完全语言是否属于完全语言是否属于P的问题等价于整个的问题等价于整个PNP问题。问题。定理定理7.1.1 设设L是是NP完全语言。那么完全语言。那么PNP当且仅当当且仅当LP。证明：根据定义证明：根据定义7.1.2和引理和引理7.1.1，容易得出结论。，容易得出结论。7.2 Cook定理定理(P类与类与NP类问题类问题)有界铺
5、砖有界铺砖：铺砖问题限定在：铺砖问题限定在sXs的正方形区域，是否存在满足铺砖条的正方形区域，是否存在满足铺砖条件的铺砖系统？件的铺砖系统？定理定理7.2.1 有界铺砖是有界铺砖是NP完全的完全的。 证明：首先证明它属于证明：首先证明它属于NP；最后证明；最后证明NP里所有语言都可归约到有界里所有语言都可归约到有界铺砖上。略铺砖上。略定理定理7.2.2(Cook定理定理)：可满足性是可满足性是NP完全的完全的。 证明：前面已经论证过证明：前面已经论证过“可满足性可满足性”属于属于NP，进一步构造把有界铺，进一步构造把有界铺砖归约到可满足性上。略砖归约到可满足性上。略定理定理7.2.3 三元可满
6、足性是三元可满足性是NP完全的完全的。 证明：它是证明：它是“可满足性可满足性”的特殊情形，所以它是属于的特殊情形，所以它是属于NP；接着构造；接着构造把把“可满足性可满足性”规约到三元可满足性上。略规约到三元可满足性上。略最大可满足性最大可满足性：给定子句集：给定子句集F和整数和整数K，是否存在满足至少，是否存在满足至少K各子句各子句的真值赋值？的真值赋值？定理定理7.2.4 最大可满足性是最大可满足性是NP完全的完全的。(证明类似三元证明类似三元)7.3 其它的其它的NP完全问题完全问题对于任一新的判定问题对于任一新的判定问题II，其，其NP完全性的完全性的论证过程应由以下四个部分组成：论
7、证过程应由以下四个部分组成：1）证明）证明II NP；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；接着构造
8、把；接着构造把“可满足性可满足性”归约到恰当覆盖归约到恰当覆盖上。略上。略定理定理7.3.2：Hamilton圈是圈是NP完全的完全的。 证明：已经论证过证明：已经论证过Hamilton属于属于NP，进一步构造把恰当覆盖归约到，进一步构造把恰当覆盖归约到Hamilton圈上。略圈上。略定理定理7.3.3无向无向Hamilton圈是圈是NP完全的完全的。 证明：把普通的证明：把普通的Hamilton圈归约到它上。略圈归约到它上。略定理定理7.3.4 旅行商问题是旅行商问题是NP完全的完全的。 证明：已知它属于证明：已知它属于NP，把无向，把无向Hamilton圈归约到它上。略圈归约到它上。略定理
9、定理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)完全可近似：无论多小的完全可近似：无论多小的e0，存在问题的多项式时间，存在问题的多项式时间e近似算法；近似算法；b)部分可近似：部分可近似：e在一个范围内，存在问题的多项式时间在一个范围内，存在问题的多项式时间e近似算法；近似算法；c)不可近似：无论不可近似：无论e多大都不存在问题的多项式时间多大都不存在问题的多项式时间e近似算法。近似算法。 完完
