第8章 NP完全性理论

❖判定问题举例：给定一个带整数权的有向图G和一 个正整数k，是否存在着一条长度小于k的哈密尔顿回 路？
❖优化问题举例：给定一个带整数权的有向图G，其 最短路径长度的哈密尔顿长度是多少？
NP完全问题
1.3 优化问题向判定问题的转换
判定问题举例：给定一个带整数权的有向图G和一个正整数k， 是否存在着一条长度小于k的哈密尔顿回路？ 优化问题举例：给定一个带整数权的有向图G，其最短路径 长度的哈密尔顿长度是多少？
for (int j=0; j<n; j++)
if (a[i] == a[j])
return yes; //修改为no
return no; //修改为yes
}
NP完全问题
2.1.5 判定问题规约的定义
❖定义：令和是两个判定问题，如果存在一个 具有如下性能的算法A，可以用多项式的时间，把 问题的实例I转换为问题的实例I，使得I与I的 答案一致，就称以多项式时间规约于，记为 p
❖定理：P类问题在补集下是封闭的
❖证明：对于P类问题中的任意问题，只要修 改相应的多项式级别算法A的代码，把返回yes的 改为返回no，把返回no的改为返回yes即可
boolean judgeEqual(int n, Elem[] a, Elem[] b){
for (int i=0; i<n; i++)
第12章 NP完全问题
1. NP完全问题概述 2. P类和NP类问题 3. NP完全问题 4. co_NP类和NPI类问题
NP完全问题
1. NP完全问题概述
1.1 Church-Turing论题和Cook-Karp论题 1.2 问题分类 1.3 优化问题向判定问题的转换

zhaotingg@
兰州城市学院数学学院
算 法 设 计 技 巧 与 分 析 · Algorithms Design Techniques and Analysis
第十章
NP完全问题
如果对任意问题类C，问题∏的补也在C中，我们说问 题类∏∈C在补运算下是封闭的。 例如，2着色问题的补可以陈述如下：给出一个图G， 它是不2可着色的吗？我们称这个问题是NOT-2-COLOR问题。 可以证明， NOT-2-COLOR问题是属于P类的。即2着色 问题在补运算下是封闭的。
zhaotingg@
兰州城市学院数学学院
算 法 设 计 技 巧 与 分 析 · Algorithms Design Techniques and Analysis
第十章
NP完全问题
定义10.5 一个判断问题Π称为是NP困难的，如果 对NP中每一个问题Π’, Π’ ∝polyΠ表示。
算 法 设 计 技 巧 与 分 析 · Algorithms Design Techniques and Analysis
第十章
NP完全问题
10.4 NP完全问题
术语“NP完全”表示NP中判定问题的一个子类，它们在下述意义 下是最难的，即如果它们中的一个被证明用多项式时间确定性算法可解， 那么NP中的所有问题用多项式时间确定算法可解，即P=NP。
颜色，所需的最少颜色数，称为G的色数，记为χ(G).
zhaotingg@
兰州城市学院数学学院
算 法 设 计 技 巧 与 分 析 · Algorithms Design Techniques and Analysis
第十章
NP完全问题
例10.3 给出一个无向图G=(V,E)，对于某个正整数k，G

12
NP-完全性理论
Karp的贡献
理查德·卡普（Richard Karp ， 1935- ） 1972 年论文 ”Reducibility among Combinatorial Problems” 发 展和加强了由库克提出的“NP完全性”理论。 尤其是库 克仅证明了命题演算的可满足问题是NP完全的，而卡普则证明了从 组合优化中引出的大多数经典问题(背包问题、覆盖问题、匹配问 题、分区问题、路径问题、调度问题等)都是NP完全问题。只要证 明其中任一个问题是属于P类的，就可解决计算复杂性理论中最大 的一个难题，即P=?NP。
SAT∈P当且仅当P=NP
Cook 于1961 年获 Michigan 大学学士学位， 1962 和 1966年分获哈佛 大学硕士与博士学位。 1966-1970 ，他在 UC Berkeley 担任助教授； 1970年加盟多伦多大学，现为该校CS 和数学系教授，他的论文开启 了NP完备性的研究，令该领域于之后的十年成为计算机科学中最活 跃和重要的研究。因其在计算复杂性理论方面的贡献，尤其是在奠 定NP完全性理论基础上的突出贡献而荣获1982年度的图灵奖。
9
P、NP及NPC类问题
NP=？P
∵确定型图灵机是非确定型图灵机的特例，∴P⊆NP 是否有NP⊆P？即是否NP=P？
美国麻省的Clay数学研究所于2000年5月24日在巴黎法兰西学院宣 布：对七个“千年数学难题”中的每一个均悬赏 100 万美元，而 问题NP=？P位列其首:
1.P问题对NP问题 2.霍奇猜想 3. 庞加莱猜想 (2002.11-2003.7 ，俄罗斯数学家佩雷尔曼在 3 篇 论文预印本中证明了几何化猜想，2006被授予菲尔兹奖) 4.黎曼假设 5.杨－米尔斯存在性和质量缺口 6.纳维叶－斯托克斯方程的存在性与光滑性 7.贝赫和斯维讷通－戴尔猜想

华中科技大学计算机科学与技术学院 jrc@
§2 P和NP
在第一章图灵机的定义中，将“协调性 条件”取消，当某个格局存在多于一 个图灵机指令符合当前格局时，从中 任选一条执行。如此定义的图灵机称 为不确定型的图灵机。此后将满足 “协调性条件”的图灵机改称为确定 型图灵机。
华中科技大学计算机科学与技术学院 jrc@
华中科技大学计算机科学与技术学院 jrc@
§2 P和NP
例 A={0,1}, C={x∈A*|x是一个合数的二进制表示} 例如 001001∈C， 0101 ∉C 可构造如下一个接受语言C的不确定型算法： 输入：x∈A* 1. 设x表示的二进制数为n，任意挑选一个正整数m，1<m<n; 2. 若m整除n，则停机；否则执行3. 3. 死循环（比如while(x==x){;;;}） x∈C当且仅当此算法运行时存在一个最终停机的计算过程。 在每个最终停机的计算过程中，只需挑选一个不超过|x| 位的二进制数，然后做一次被除数为|x|位二进制数的除 法，判断余数是否为0即可，计算时间不超过一个关于 |x|的多项式。 据此，C∈NP 注意 ：如果将“任意挑选一个”改为“遍历”，可以得到一 个指数（为什么？）计算时间的确定型算法。
华中科技大学计算机科学与技术学院 jrc@
§2 P和NP
定理2 若R ≤pQ ， Q≤pL，则R≤pL 定理3 若Q、L ∈P， Q、L≠φ， Q、L≠A*，则 Q≤pL， L≤pQ
华中科技大学计算机科学与技术学院 jrc@
§2 P和NP
定义 语言L被称作为NP难度的（NP-hard） 是指对任一语言Q∈NP都有Q≤pL； 如果L为NP难度的且L∈NP，则称L是NP 完全的（NP-complete）。 若语言L为NP难度的，则：若L的判定问题， 即x∈?L问题易解，则对任何属于NP的语 言Q， Q的判定问题都易解。 在这个意义 上L具有了不不低于NP中所有语言的判定 难度。 语言L为NP完全的，其意义是指L是NP中 判定难度最高的语言。