NP完全性精讲

Lecture 10. NP完全性理论清华大学软件学院清华大学 1内容提要•计算模型与计算复杂度关系•问题分类：【P】与【NP】类•NP－难【hard】问题，NP完全集•第一个NPC问题和NPC问题集•如何证明一个问题是NPC问题涉及到的算法理论基础•原则上是否存在一般数学问题的解题步骤的判决问题【希尔波特第十问题】•图灵机的停机问题：是否存在一个图灵机，他可以回答其它图灵机是否停机【既算法是有界的】•图灵公理：凡是可计算的函数都可以用一台图灵机来计算•P－NP－NPC问题定义及其猜想：NPC是一类不可以在多项式时间内计算的问题。

清华大学 3明代数学家程大位著《算法统宗》中关于珠算的插图机械式手动计算机清华大学 5机械计算机•法国数学家、哲学家帕斯卡在1642年发明了一种机械计算机，并与1649年取得专利。

帕斯卡的计算机采用一种齿轮系统，其中一小轮转十个数字，下一个小轮便转动一个数字，通过齿轮系的联动，可以进行加法和减法的运算.图灵•大半个世纪以来，数学家、计算机科学家提出了各种各样的计算模型都被证明是同图灵机器等价的。

这一理论已被当成公理，它不仅是计算机科学的基础，也是数学的基础之一。

为纪念英国数学家Turing(1912-1954) 而设立的图灵奖成为计算机界的诺贝尔奖.清华大学7图灵机模型图灵机定义•一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且•1) •2) •3) 集. •4) •5) •6) •7) Q 是状态集.∑是输入字母表,不包括特殊空白符号︺. Γ是带字母表,其中: ︺∈Γ,∑是Γ的子δ: Q×Γ→Q×Γ×{L,R}是转移函数. q0∈Q是起始状态.q1∈Q是接受状态.q2∈Q是拒绝状态,且q2≠q1图灵机模型•图灵机模型用一个无限长的带子作为无限存储, 它还有一个读写头,这个读写头能在带子上读, 写和移动: 开始时,带子上只有输入串,其它地方都是空的.当它需要保存信息时,读写头就把信息写在带子上.为了读某个输入或写下的信息,带子可能将读写头往回移动到这个信息所在的地方.这样读,写和移动,机器不停的计算, 直到产生输出为止.机器实现设置了两种状态: 接受或拒绝清华大学9多带图灵机,•和普通图灵机相似,只是有多个带子,每个带子都有自己的读写头,用于读和写.如图清华大学11非确定性的图灵机•非常容易理解,在计算的任何时刻,机器可以在多种可能性中选择一种继续进行.它的计算是一课树,不同的分枝对应着机器不同的可能性.如果某个计算分枝导致接受状态,则接受该输入.与多带图灵机相同的是,它的计算能力与普通图灵机也是一样的.当然他的计算能力就不一样了。

3.4 NP完全性的证明一、六个基本的NPC问题三元可满足性问题(3SAT)三维匹配问题(3DM)顶点覆盖问题（VC）团的问题哈密顿回路(HC)均分问题二、基本NP完全问题的证明三、NP完全问题的证明方法一、六个基本NP完全问题3SAT实例: 有穷布尔变量集U 和U上的子句集C={c1,c2,...,cm},其中|ci|=3, 1≤i≤m.问: 对于U是否存在满足C中所有子句的真值赋值？3DM实例: 集合M ⊆W×X×Y, 其中W,X,Y互不相交, 且|W|=|X|=|Y|=q.问: M是否包含一个匹配, 即是否存在子集M’⊆M使得|M’|= q且M’中任意两个元素的三个坐标都不相同?肯定实例：W={a1,a2,a3,a4},X={b1,b2,b3,b4},Y={c1,c2,c3,c4}M={(a1,b2,c1),(a1,b1,c1),(a2,b1,c2),(a2,b2,c1), (a3,b3,c3),(a4,b4,c4),(a4,b2,c1)}VC实例: 图G=(V,E), 正整数k≤|V|.问: G中是否存在大小不超过k的顶点覆盖, 即是否存在子集V’⊆V,使得|V’|=k, 且对每条边{u,v}∈E都有u∈V’或v∈V’?团实例: 图G=(V,E), 正整数J≤|V|.问: G是否包含大小不小于J的团, 即是否存在子集V’⊆V,使得|V’|≥J, 且V’中每两个顶点都由E中的一条边连接?独立集实例：图G=(V,E)，正整数J≤|V|问：G中是否包含大小不小于J的独立集，即是否存在V’⊆V, 使得|V’|≥J，且∀u,v∈V’，{u,v}∉E?HC实例: 图G=(V,E),|V|=n.问: G 中是否包含一条哈密顿回路, 即是否有G 的顶点排列><n j j j v v v ,...,,21?},{,1,},{11E v v n i E v v j j j i j n i ∈<≤∈+∑=∑-∈∈'')()(A A a A a a S a S 使得均分实例: 有穷集合A, ∀a ∈A 有”大小”S(a)∈Z +问: 是否存在子集A ’⊆ A 使得证明顺序均分HC 团（独立集）1．3SAT∈NPC证明思路证3SAT∈NP将SAT的实例变换成3SAT的实例：根据子句中的文字个数k 分别处理1个子句转变成多个子句保证每个子句含有3个文字转变前与转变后的真值不变证显然3SAT属于NP.设U={u1,u2,...,un}, C={c1,c2,...,cm}是SAT的任何实例.对于C中任意子句c j ={z1,z2,...,zk},构造新增的变量集Uj ’和子句集Cj’.}},,}{,,{},,,{},,,{{'},{'21121121121121j j j j j j j j j j j j y y z y y z y y z y y z C y y U ==C j ’被满足⇔c j 被满足.若k=2, c j ={z 1,z 2}, 则}},,{},,,{{'}{'1211211j j j j j y z z y z z C y U ==C j ’被满足⇔z 1+z 2为真⇔c j 被满足.若k=3, 则U j ’= ∅C j ’= {c j }若k=1, c j ={z 1}, 则},,{},,,{},,,{{'},{'54223112121z z y y z y y z z C y y U j j j j j j j j ==c j 可满足⇔z 1+z 2+...+z 5为真⇒C j ’可满足如z 1+z 2为真, 则y j 1= y j 2 = F ;如z 3为真, 则y j 1= T,y j 2 = F ；如z 4+z 5为真, 则y j 1= T,y j 2 = T .反之, 若C j ’可满足而c j 不满足, 则z 1+z 2+...+z 5为假, 即z 1,z 2,...,z 5全为假, 必须y j 1=T,y j 2 =T, 最后的子句不满足.若k>3, 例如c j = {z 1,z 2,...,z 5}, 则一般若c j ={z 1,z 2,...,z k }, k>3}},,{{}41:},,{{}},,{{'}31:{'1312121k k k ji ji i j j j i j j z z y k i y z y y z z C k i y U --++⋃-≤≤⋃=-≤≤=令U ’= U ⋃U 1’⋃U 2’⋃...⋃U m ’C ’= C 1’⋃C 2’⋃...⋃C m ’下面证明f是多项式变换.易见若t满足C’, 则t满足C. 假若t不满足cj，则z 1,z2,…,zk全为假，只能有Tyyy k jjj====-321...C’的最后一个字句不满足.反之，设t:U→{T,F}是满足C的真值赋值, 将U’－U的变量分成U1’, U2’, ..., Um’, 且Uj’的变量只出现于子句Cj ’中。

1§1.3 NP 完全性理论如何理解问题的难解？易解？多项式运行时间？⏹多项式的运行时间认为是易解算法，当然，你认为θ(n100)难解，但次数如此高的多项式时间问题非常少，且一般都会找到一个更有效的多项式时间算法。

⏹对很多合理计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以用多项式时间获得解决。

2如何理解问题的难解？易解？多项式运行时间？多项式时间可解问题类具有很好的封闭性。

比如一个多项式时间算法输出给另一个多项式时间算法作为输入，或被另一个多项式时间算法作为子程序常数次调用，这样的组合算法运行时间也都是多项式的。

3⏹一般来说，将可由多项式时间算法求解的问题看成易处理的问题，而把需要超多项式时间才能解决的问题看作难处理问题。

⏹“NP完全”（NP-Complete）问题，它的状态是未知的，迄今为止，既没有人找出求解NP完全问题的多项式算法，也没人能够证明对这类问题不存在多项式时间算法。

⏹P≠NP问题，自1971年提出以后，已经成为理论计算机科学研究领域中，最深奥和最错综复杂的开放问题之一了。

45⏹从表面上看，有些NP 完全问题有着与多项式时间算法的问题非常相似的特点，这很诱惑。

⏹最短与最长简单路径：有向图G=(V,E)，单源最短路径可在O(|V|2)时间内完成，但寻找两个顶点间最长简单路径（无重复顶点）问题是NP 完全的。

⏹欧拉游程和哈密顿回路：有向图G=(V,E)，欧拉游程指一个回路，遍历途中每条边一次，但可能不止一次的访问同一个顶点，这可在O(|E|)时间内找到。

哈密顿回路也是一个回路，包含V 中每个顶点。

确定有向图是否存在哈密顿回路的问题是NP 完全的。

探讨这样三类问题：P、NP、NPC（NP 完全问题）⏹NPC类，称NP完全的(NP-complete)，属于NP的一个最难的子类。

如果一个问题属于NP，且与NP中任何问题一样“难的”。

⏹有宣称：如果任何NPC问题可以在多项式时间内解决，则NP中所有问题都有一个多项式时间的算法，即有P=NP了。