第10章NP完全问题(自己写的)
- 格式：ppt
- 大小：708.50 KB
- 文档页数：23
下载文档原格式
合集下载
算法分析设计NP完全问题PPT课件
if(a[j]==x) { cout<<j;
Success();
执行时间都为O(1) //不确定算法成功终止
}
cout<<-1; Failure(); }
若算法执行中需作出一系列的Choice函 数//不选确择定，算当法且失仅败当终C止hoice的任何一组选 择都不会导致成功信号时，算法在O(1)时 间不成功终止。
在不不确确定定搜机索上算执法行：的算法称为不确定算法(non
dveotiedrSmeianricsht(iicntaal[g],oTrxit)hm如)果。一个判定问题实例的解为真，
Hale Waihona Puke {Choice函数每一次总能在O(1)时间
int j=Choice(0,n-1); 内//从做{出0,1导,.致..,n成-1功}中的任正意确选选取择一。个值
即： ✓求解Q1的确定算法是通过调用求解Q2的确定算法完 成的， ✓对Q2算法实施的调用过程所需的时间是多项式时间 的。 那么：只要对问题Q2存在多项式时间求解算法，问题 Q1就能在多项式时间内得以求解。
第15页/共29页
约化存在以下性质： 性质10-1 若Q1∈P，Q2∝Q1，则有Q2 ∈P。 性质10-2 （传递性） 若Q1∝Q2，Q2∝Q3，则Q1∝Q3。
因为：对n个布尔变量赋值需要O(n)时间，计算公式 E(x,n)的时间为O(e)，e是公式长度。
所以，可满足性问题的不确定算法时间为O(n+e)。
第13页/共29页
10.1.3 P类和NP类问题
P类问题：可在多项式时间内用确定算法求解的判定 问题。 NP类问题：可在多项式时间内用不确定算法求解的 判定问题。（多项式时间内可验证问题的解。）
参考资料NP完全问题-一些重要的概念.ppt
2019/3/20 8
第一个难解的“可判定”问题是在六十年代初获 得的，它是Hartmanis和Stearns［1965]的复杂性 “谱系”工作的一部分，但是，这些结果只包括一些 “人工制造的”问题，它们被专门构造成具有所需要 的性质。直到七十年代初，Meyer和 Stockmeyer[1972］，Fischer和Rabin［1974］以及 其他人终于成功地证明某些“自然的”可判定问题是 难解的，这些问题包括自动机理论、形式语言理论以 及数理逻辑中以前研究过的各种问题。实际上，他们 的证明表明甚至用“非确定型” （nondeterministic)计算机模型也不可能在多项式 时间内解这些问题，这种“非确定型”计算机模型具 有执行无限多个独立的并行计算序列的能力。这种 “不合理的”计算机模型在NP完全性理论中起着重要 的作用。 2019/3/20 9
2019/3/20
10
3、NP完全问题
• 可以用“非确定型”计算机通过多项式时间算法求解 的问题称为“NP类”问题。理论工作者们一方面继续 寻找更有力的方法来证明问题的难解性，同时又在努 力研究就难度而言各种问题相互联系的方式。发现问 题之间的这种相互联系常常可以给算法设计人员提供 有用的信息。证明两个问题相关的基本方法是通过给 出一个构造性变换把第一个问题的任一实例映射到第 二个问题的一个等价的实例，从而把第一个问题“归 约”为第二个问题。这样的变换提供了一个手段，把 解第二个问题的任何算法转变成解第一个问题的相应 的算法。
2019/3/20
16
实用中，知道一个问题是NP完全的就给我们提供 了有价值的信息，告诉我们采用什么样的途径可以是 最富有成效的。一定不要去优先寻找有效的、精确的 算法。现在比较适当的途径是集中精力致力于其他较 低目标的方法。例如，你可以寻找解决这个问题的各 种特殊情况的有效算法。寻找在大多数情况下看来能 快速运算的算法，虽然不能保证它在任何情况下都能 快速地运算。或者你甚至可以放松问题的某些方面， 寻找一个只能给出满足大部分要求的快速算法。简言 之，NP完全性理论的初步应用是帮助算法设计人员找 到最有可能得到有用的算法的努力方向。
第一个难解的“可判定”问题是在六十年代初获 得的，它是Hartmanis和Stearns［1965]的复杂性 “谱系”工作的一部分，但是，这些结果只包括一些 “人工制造的”问题，它们被专门构造成具有所需要 的性质。直到七十年代初，Meyer和 Stockmeyer[1972］，Fischer和Rabin［1974］以及 其他人终于成功地证明某些“自然的”可判定问题是 难解的，这些问题包括自动机理论、形式语言理论以 及数理逻辑中以前研究过的各种问题。实际上，他们 的证明表明甚至用“非确定型” （nondeterministic)计算机模型也不可能在多项式 时间内解这些问题，这种“非确定型”计算机模型具 有执行无限多个独立的并行计算序列的能力。这种 “不合理的”计算机模型在NP完全性理论中起着重要 的作用。 2019/3/20 9
2019/3/20
10
3、NP完全问题
• 可以用“非确定型”计算机通过多项式时间算法求解 的问题称为“NP类”问题。理论工作者们一方面继续 寻找更有力的方法来证明问题的难解性，同时又在努 力研究就难度而言各种问题相互联系的方式。发现问 题之间的这种相互联系常常可以给算法设计人员提供 有用的信息。证明两个问题相关的基本方法是通过给 出一个构造性变换把第一个问题的任一实例映射到第 二个问题的一个等价的实例，从而把第一个问题“归 约”为第二个问题。这样的变换提供了一个手段，把 解第二个问题的任何算法转变成解第一个问题的相应 的算法。
2019/3/20
16
实用中，知道一个问题是NP完全的就给我们提供 了有价值的信息，告诉我们采用什么样的途径可以是 最富有成效的。一定不要去优先寻找有效的、精确的 算法。现在比较适当的途径是集中精力致力于其他较 低目标的方法。例如，你可以寻找解决这个问题的各 种特殊情况的有效算法。寻找在大多数情况下看来能 快速运算的算法，虽然不能保证它在任何情况下都能 快速地运算。或者你甚至可以放松问题的某些方面， 寻找一个只能给出满足大部分要求的快速算法。简言 之，NP完全性理论的初步应用是帮助算法设计人员找 到最有可能得到有用的算法的努力方向。
第十章 NP完全问题
第十章 NP 完全问题10.1 引言首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。
算法的复杂性是指解决问题的一个具体的算法的执行时 间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。
比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。
问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。
如果∏是任意一个问题，对∏存在着一个算法，他的时间复杂度是)(k n O ，其中n 是输入规模，k 是非负整数，则认为存在一个解问题∏的多项式时间算法。
多项式时间算法是一个有效算法。
把存在多项式时间算法的问题，称为易解决问题；把时间复杂度是以指数函数或排列时间算法的问题，称为难解问题。
为什么用多项式作为划分的标准呢？1） 对于使用的多项式算法来说，多项式的次数很少大于三；2） 多项式时间可解问题类具有很好的封闭性。
即加、减、组合等运算封闭；3） 对很多合理的计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以在多项式时间内获得解决。
有两类问题：一类是判定问题，另一类是优化问题。
判定问题的只牵涉到两种情况：yes 或no。
优化问题则牵涉到极值问题（最大化或最小化）。
判定问题很容易转换为优化问题。
为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。
任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？…从A 到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。
NP完全问题讲解
x1
x2
x4
x1
x2
x1 x2
x3
x2
x3
x4
x4
The formula is satisfied if and only if the Graph has a 4-clique End of Proof
Fall 2006 Costas Busch - RPI 13
NP-complete Languages
A
in polynomial time:
w:
Fall 2006
Costas Busch - RPI
1. Compute f ( w) 2. Run M on input f ( w) 3. If f (w ) B acccept w
5
Example of a polynomial-time reduction:
Fall 2006
Costas Busch - RPI
9
(x1 x2 x4 ) (x1 x2 x4 ) (x1 x2 x3 ) (x2 x3 x4 )
Transform formula to graph. Example:
Create Nodes:
x1
Clause 2
clause Each clause has three literals
Language:
3CNF-SAT ={
w
:
w
is a satisfiable 3CNF formula}
7
Fall 2006
Costas Busch - RPI
A 5-clique in graph
G
Language:
CLIQUE = { G, k : graph G contains a
如何用整数规划求解NP完全问题
如何⽤整数规划求解NP完全问题如何⽤整数规划求解NP完全问题⼀、NP完全问题NP完全问题是⼀类具有⾮常⾼难度的组合最优化问题，所有NP完全问题都是NP难问题。
虽然P问题是⽐较容易的问题，NP问题却不⼀定是困难问题，必须看见NP完全或者NP难这样的字才能说这个问题求解起来很困难。
经常听砖家说，NP完全/NP难问题不能⽤整数规划求解。
实际情况怎样？实事证明砖家的话只能信⼀半：）。
这⾥咱就看看⽤整数规划求解⼀个NP完全问题⾏也不⾏。
这⾥有⼀个货真价实的整数规划问题——划分问题（The partition problem）。
问题是：给定⼀个⼤⼩不等的整数集合，问是否可以把这些整数划分成两个集合，任何⼀个整数或者在集合S1中或者在S2中，但不能同时在两个集合中；对任意给的⼀个整数集合，请设计算法，解决是否存在⼀个划分，使得S1种整数之和恰好等于S2集合的整数之和。
⼆、建⽴整数规划模型对每个整数定义⼀个0-1变量xi, xi=1 表⽰第i个整数位于集合S1中， xi=0表⽰第i个整数位于S2中。
⽤s1表⽰第⼀集合的整数之和，⽤s2表⽰第⼆个集合⾥的整数之和。
即：设d是s1和s2之间差的绝对值。
于是：我们只要极⼩化d就可以了，即：完整模型：三、上⾯的模型的⽂本表达上⾯的模型不只是⽤来摆摆看的，还可以真的被求解哈。
我们需要把模型写成⽂本格式（Leapms建模语⾔格式），让计算机理解。
⽬标函数就写成min d加上其余约束部分（注意西格玛符合的写法）subject tos1=sum{i=1,...,n}x[i]S[i]s2=sum{i=1,...,n}((1-x[i])S[i])d>=s1-s2d>=s2-s1加上符号说明（符号必须说明，不然计算机不知道哪些是常数，哪些是变量）wheren is an integerS is a sets1,s2,d are variables of numberx[i] is a variable of binary|i=1,...,n加上数据（注意整数个数是从集合S上⾃⼰数出来的）data_relationn=_$(S)dataS={11,47,159,137,85,47,142,35,119,61,88,175,13,96,-11,176,126,15,98,46,163}四、求解把如下完整模型贴到记事本上，保存为 partition.leap⽂件。
NP完全的问题
NP完全的问题一个NP－完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。
P是所有可在多项式时间内用确定算法求解的判定问题的集合。
NP 问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。
令L1和L2是两个问题，如果有一确定的多项式时间算法求解L1，而这个算法使用了一个在多项式时间内求解L2的确定算法，则称L1约化为L2。
如果可满足性约化为一个问题L，则称L问题是NP-难度的。
如果L是NP难度的且L（－NP，则称L是NP－完全的。
NP并不是NON-POL YNOMIAL，把NP说成是NON-POL YNOMIAL，是望文生义，读书不求甚解。
事实上，如果你能够证明某个NP问题是个NON-POL YNOMIAL的问题，你就可以去领那七个百万美元数学大奖中间的一个了。
数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是NP=P？的问题。
问题就在这个问号上，到底是NP等于P，还是NP不等于P。
证明其中之一，便可以拿百万美元大奖。
这个奖还没有人拿到，也就是说，NP 问题到底是Polynomial，还是Non-Polynomial，尚无定论。
NP里面的N，不是Non-Polynomial的N，是Non- Deterministic，P代表Polynomial倒是对的。
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数，则这种可以在多项式时间内解决的判定性问题属于P类问题。
P类问题就是所有复杂度为多项式时间的问题的集合。
通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。
有些问题很难找到多项式时间的算法（或许根本不存在），例如“找出无向图中哈米尔顿回路”问题。
但如果给了该问题的一个答案，可以在多项式时间内判断这个答案是否正确。
NP完全问题(纯理论)
NP类问题举例—求真因子问题
国王： 顺序算法 宰相： 并行算法
是否所有的难解问题通过并行计算使其在多项式内可 解？
关于并行算法：当将一个问题分解到多个处理器上解 决时，由于算法中不可避免地存在必须串行执行的操 作，从而大大地限制了并行计算机系统的加速能力。
NP类问题举例—求真因子问题
阿达尔定律:串行执行操作仅占全部操作1%，解 题速度最多也只能提高一百倍。
以多项式作为分界函数？
原因有两个： 一、常见算法大致分为两类： 一类是多项式时间内可实现的 另一类需要指数时间（O(cn))
多项式时间算法的可实现性远大于指数时间算法。 （参见P8，表1.2)
以多项式作为分界函数？
二、多项式时间算法与计算模型无关 算法的研究依赖于计算模型。在不同类型计算模型 上实现算法，计算时间不同。
SATISFIABILITY∝p3-SATISFIABILITY
几个典型的NPC问题
图的着色问题(COLORING) 判定问题：COLORING 输入：无向图G=(V,E) 问题：是否可用ｋ种颜色为图Ｇ的顶点着色，使 得相邻顶点不会有相同颜色。
3-SATISFIABILITY∝pCOLORING
定义12.3 令П 是一个判定问题，如果： (1) П ∈NP； (2) 对NP中的所有问题П ′∈NP，都有 П ′∝pП ； 则称判定问题П 是NP完全 (NPC)的。
P类、NP类、NPC类问题关系
根据定义，可用如下图表示三者之间的关系：
NP
Ｐ
NPC
P类、NP类、NPC类问题关系
对NPC问题，有个重要性质 对NPC类中的一个问题，如果能够证明用多项式 时间的确定性算法来进行求解或判定，那么， NP中的所有问题都可以通过多项式时间的确定性 算法来进行求解或判定。
NP完全问题证明
均分∈ 8.5.5. 均分∈NPC 子集A :1≤ 子集A’ = {ai:1≤i≤k} 满足
a∈ A'
∑ s( a ) = B
当且仅当 M’ = {mi: ai∈A’}是M的匹配 } A的最后两个元素b1,b2 的最后两个元素b
s ( b1 ) = 2 ∑ s ( a i ) − B
i =1
k
s ( b2 ) = ∑ s ( a i ) + B
均分∈ 8.5.5. 均分∈NPC
构造A 构造A，|A| = k +2 对应于每个m 对应于每个mi = (wf(i),xg(i),yh(i)) 有ai. 为二进制数，分成3q 3q段 每段有p log(k+1) s(ai)为二进制数，分成3q段，每段有p = log(k+1)位,共计 3pq位 每段对应一个W 3pq位，每段对应一个W∪X∪Y中的元素. Wf(i),xg(i),yh(i) 所代 中的元素. 表的段的最右位为1 其它为0. 表的段的最右位为1，其它为0.
均分∈ 8.5.5. 均分∈NPC
实例：有穷集A s(a)∈ 实例：有穷集A，∀a∈A, s(a)∈Z+. 是否存在A ⊆ 问：是否存在A’⊆A，使得
a∈ A'
∑ s( a ) =
a∈ A− A均分是NP类问题。下面将3DM变换到均分问题 显然均分是NP类问题。下面将3DM NP类问题 3DM变换到均分问题 3DM的实例 的实例， 设W,X,Y,M ⊆ W×X×Y 是3DM的实例， 其中|W| q， 其中|W| = |X| = |Y| = q， W = {w1,w2,… ,wq} X = {x1,x2,… ,xq} Y = {y1,y2,… ,yq} M = {m1,m2,… ,mk}
10第十章 NP完全问题
2可满足问题：给出一个合取范式（CNF）形 式的布尔表达式f，这里每个字句恰好由两 个文字组成，问f是可满足的吗？
如果对于任意问题c，Π的补也在c中，我 们说问题类Π∈c在补运算下是封闭的。例如， 2着色问题的补可以陈述如下：给出一个图G， 它是2不可着色的吗？我们称这个问题为NOT2-COLOR问题。
还有很多计算模型，此处略。
量子计算模型是什么样子呢？ 本章的讲解是初步入门，不讨论建立在相应计算模型上的 算法讨论。
10.1 引 言 前面所有的算法的运行时间可以用低次 多项式表示。现在有这样一类问题，这些问 题至今还没有找到有效的算法，而且在将来 也不大可能发现它们的有效算法。
设Π是任意问题，如果对问题Π存在 一个算法，它的时间复杂性是O(nk)，其中n 是输入大小，k是非负整数，我们说存在求 解问题Π的多项式时间算法。
下面证明它是属于P类的。 由于2着色问题在P中，存在一个确定性 算法A，当展示一个2可着色图时，它停机 并回答yes，在展示一个图不是2可着色图 时，它停机并回答no。通过在算法A中简单 的交换yes和no，能够得出问题NOT-2COLOR的一个确定性算法。这样有如下定 理。
定理 10.1 P类问题在补运算下是封闭的
10.3 NP类(Nondeterministic Polynomial) NP类由这样的问题Π组成，对于这些问题 存在一个确定性算法A，该算法在对Π的一个 实例展示一个断言解时，它能在多项式时间 内验证解的正确性。即如果断言解导致答案 是yes，就存在一种方法可以在多项式时间内 验证这个解。
为了较形式地定义这个类，必须首先定义不 确定性算法的概念。对于输入x，一个不确 定性算法由下列两个阶段组成。 (a) 猜测阶段 在这个阶段产生一个任意字 符串y，它可能对应于输入实例的一个解， 也可以不对应解。事实上，它甚至可能不 是所求解的合适形式，它可能在不确定性 算法的不同次运行中不同。它仅仅要求在 多项式步数内产生这个串，即在O(ni)时间 内，这里n=|x|, i是非负整数。对于许多问 题，这一阶段可以在线性时间内完成。
P问题、NP问题、NP完全问题和NP难问题
P问题、NP问题、NP完全问题和NP难问题在讲P类问题之前先介绍两个个概念：多项式，时间复杂度。
(知道这两概念的可以⾃动跳过这部分)1、多项式：axn-bxn-1+c恩....就是长这个样⼦的，叫x最⾼次为n的多项式....咳咳，别嫌我啰嗦。
有些⼈说不定还真忘了啥是多项式了。
例如第⼀次看到的鄙⼈→_→2、时间复杂度我们知道在计算机算法求解问题当中，经常⽤时间复杂度和空间复杂度来表⽰⼀个算法的运⾏效率。
空间复杂度表⽰⼀个算法在计算过程当中要占⽤的内存空间⼤⼩，这⾥暂不讨论。
时间复杂度则表⽰这个算法运⾏得到想要的解所需的计算⼯作量，他探讨的是当输⼊值接近⽆穷时，算法所需⼯作量的变化快慢程度。
举个例⼦：冒泡排序。
在计算机当中，排序问题是最基础的，将输⼊按照⼤⼩或其他规则排好序，有利于后期运⽤数据进⾏其他运算。
冒泡排序就是其中的⼀种排序算法。
假设⼿上现在有n个⽆序的数，利⽤冒泡排序对其进⾏排序，①⾸先⽐较第1个数和第2个数，如果后者>前者，就对调他们的位置，否则不变②接着⽐较第2个数和第3个数，如果后者>前者，就对调他们的位置，否则不变③⼀直向下⽐较直到第n-1和第n个数⽐较完，第⼀轮结束。
（这时候最⼤的数移动到了第n个数的位置）④重复前三步，但是只⽐较到第n-1个数（将第⼆⼤的数移动到第n-1个数位置）⑤持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。
举个实例：5,4,3,2,1，对其进⾏排序，先是⽐较5跟4变成4,5,3,2,1，第⼀轮结束后变成43215，可以计算，当对其排序完正好要经过4+3+2+1=10次⽐较，当然这是最复杂的情况，即完全反序。
可以知道对于n个数，⾄多要经过1+2+...+n-1即(n^2-n)/2次⽐较才能排好序。
这个式⼦⾥n的最⾼次阶是2，可知道当n→∞时，⼀次性对其⽐较次数影响很⼩，所以我们把这个算法的时间复杂度⽐作：o(n^2)。
取其最⾼次，可以看出，这是⼀个时间复杂度为多项式的表⽰⽅式。
NP完全问题研究及前景剖析
收稿日期：2015-08-17基金项目：湖北省自然科学基金项目（2014CFC1121）作者简介：杜立智（1964）,男,湖北黄冈人,副教授,硕士.研究方向：计算机算法；计算数学；计算复杂性.文章编号：1674-2869（2015）10-0073-060引言对P 和NP 问题的研究,关键有两个方面,第一是对相关概念的正确理解和把握,第二是正确的研究方向与正确的研究方式方法.对于第一点,由于相关概念相当复杂抽象,存在着许多理解上的谬误.甚至一些翻译过来的教科书都存在这些谬误,从而影响了该专业的学生正确理解掌握相关概念.对于第二点,关键是倾向于以NP 等于P 为出发点还是相反.不同的出发点,对研究的成功与否,起着至关重要的作用.而在所有NP 相关问题中,NP 完全无疑是最重要的概念.事实上,对NP 完全及其相关概念的透彻理解,是深入研究NP 问题,尤其是研究NP 与P 的关系问题的关键.谈到NP 完全,又不能不涉及到多项式归约.本文的目的是,通过分析与NP 问题相关的核心概念,并通过对抽象定义的解析结合对认识谬误的剖析,揭示其实质.本文的关键点是,深入剖析NP 完全问题时间复杂度的逻辑内涵,同时通过对多个实际问题的分析,给出解决NP 完全问题的启发式思路,从而为该领域的研究者在概念和研究方向的正确把握上提供参考.1NP 和NP 完全问题的起源与基本思想及其影响和发展NP 问题是随着计算复杂性理论的产生而出现的.根据计算复杂性理论,所有科学问题按其解决时间可分为三大类：多项式类㊁指数类和不可解类.但要确定某个具体的问题到底属于哪一类,往往并非一件容易的事情,尤其是对少数难度大的问题[1-2].在理论计算机领域,对这三类问题的研究本来就浩瀚和深不可测,随着NP 问题的出现,事情就更复杂了.NP 问题是与确定性图灵机和非确定性图灵机的概念一起出现的[3].这两个概念相当抽象,极难透彻理解掌握,从而更加为NP 问题蒙上了一层神秘色彩.通俗地讲,NP 问题是 多项式验证 问题.也就是说,若是有了某个NP 问题的解,要判断这个解是否正确,这个判断可以在多项式时间内完成.至于求解这个问题到底需要多少时间,先撇开.自从NP 问题出现以后,学术界长时间对此进行了大量的投入及研究,尽管取得了不少研究成果,由于NP 问题的难度和深度,迄今为止,依然不NP 完全问题研究及前景剖析杜立智，陈和平，符海东武汉科技大学计算机科学与技术学院，湖北武汉430065摘要：P vs.NP 是理论计算机领域最重要的课题之一,而其中的核心是NP 完全问题.由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误.主要是：NP㊁NP 完全概念理解谬误,确定性及非确定性图灵机的概念模糊不清,P 与NP 关系的误读,NP 问题研究方向的误导等.本文分析了这些谬误,并揭示了相关概念的实质.通过不同角度多方位分析,对NP 完全问题可能的解决途径和研究方向,提供了启发式思路.关键字：确定性图灵机；非确定性图灵机；NP 完全问题中图分类号：TP3-0文献标识码：Adoi ：10.3969／j.issn.1674-2869.2015.10.014武汉工程大学学报第37卷能确定NP到底属于上述三类问题中的哪一类.可以确定两点,其一是NP问题空间复杂度是多项式,其二是,NP问题时间复杂度的上限是指数型.所以,任何NP问题要么是多项式,要么是指数型[4],而不可能是不可解的问题.不过,要确定NP到底是不是属于多项式,确定这一点本身倒可能是不可解问题.不少专家提出了这样的判断和疑问. 1937年,英国计算机科学家,同时也是计算复杂性理论开山鼻祖的图灵提出了一种自动机模型,后来被人们称作图灵机,并论证了图灵机的可计算功能.图灵机模型的提出不仅为现代计算机的设计奠定了理论基础,同时也成为引出和研究NP问题的工具.后进一步分为确定性图灵机（DTM）和非确定性图灵机（NDTM）两类.这两个概念在教科书中的定义高度抽象,难以把握.笔者在这里用通俗的语言加以剖析.确定性图灵机是现代计算机的理论模型,可以认为现代计算机是对图灵机理论模型的实现.其计算功能与现代计算机等价,但还是有根本的不同,前者更抽象.笔者曾经用确定性图灵机进行了编程练习,解决同样的问题,比当今流行的计算机语言编程要难得多.而非确定性图灵机则纯属理想的理论模型,现实中无法实现.P类问题也定义为在确定性图灵机上能在多项式时间内解决的问题；NP类问题则是在非确定性图灵机上能在多项式时间内解决的问题.非确定性图灵机的最大特点就是具有并行运算能力.但请注意正确理解它的关键是,这个并行并不是无限制的.它只能进行 分叉 式的并行,而不能按许多甚至无数平行线 平行 方式地并行.若是后者,那非确定性图灵机就不仅能解决NP问题,指数型问题也能一块解决了.用一颗n层的k叉树来描述确定性非确定性图灵机的区别无疑能说明问题,可以肯定所有NP问题都可以翻译成这个模型.对于这样一棵树,其节点数目是指数型,k的n次方.当然这些节点之间有统一的联系规律,这个规律信息是多项式.要寻找其中一个点,以及从顶点到这个点的一条路径,非确定图灵机从顶点开始向下,在每一个分叉处能并行地同时向所有分支走下去,从而,最多n步就能达到目的；而确定性图灵机无并行能力,它需要遍历整个树,才能保证找到目标.当然,也不排除有高超的算法使其能快速得到结果.显而易见,所有多项式问题,也就是P类问题,肯定属于NP.因为能在多项式时间内计算出结果的,必然也能在多项式时间内验证结果.但NP是否属于P成了该领域的最大难题,迄今无法确定.该问题的解决不仅能在该领域带来理论上的重大突破,并且也能对许多重要的问题的实际计算具有意义.1971年,NP问题的研究取得了里程碑的突破.加拿大著名计算机科学家史蒂文-库克证明了存在具有NP完全性质的NP问题[5],这就是可满足性问题（SAT）,它也是人类发现的首个NP完全问题（NPC）.所谓某问题具备NP完全性,也就是,任何NP问题的求解都可以多项式转化到对该问题的求解.库克构造了一般NP问题,也就是任意NP问题多项式转化为SAT问题的转化方法和公式,从而完成了NP完全的证明.其逻辑结果是：如果能得到可满足性问题的多项式时间算法,那就意味着所有NP问题都具有多项式时间算法,即NP等于P.请注意证明某NP问题具有NP完全性,通常是一道艰难的工作,普通的NP问题并不具备这一特性.而大量的NP问题其实就是非常简明的P问题.不少论文书刊中,经常使用这样的说法：某问题是NP,故无有效算法.这当然是一种谬误,是混淆了NP与NP完全的概念.NP和NP完全问题的出现,对计算机算法和计算复杂性领域,产生了重大而深远的影响.随着第一个NP完全问题的发现和证明,兴起了对这类问题之间的多项式转化研究.在教科书中通常将这种转化称为 归约 [6].注意理解多项式归约必须把握两个关键点：一是转化本身所需的时间是多项式,二是转化后对原问题计算规模的扩大,不超出多项式的范围.例如,若需要将具有n 个变量的3SAT问题按多项式规约转化为对另一NP问题的求解,那么,转化所需的时间不能超出n 的多项式函数,同时,设转化后后一问题的大小规模为m,m也不能超出n的多项式函数.若是m在n的基础上呈指数型放大,即使转化本身所花的时间很快,那当然也不能称作多项式归约.长期以来,多项式转化的研究一直经久不衰.它主要有两个方面的价值.从70年代初开始,前期的研究主要是为了发现NP完全问题.那时候每发现一个NP完全问题,就是一个较轰动的大成果.如今这个已经不那么重要了.但由于NP完全问题74第10期之间的多项式转化性质,若得到了一个问题的高效算法,则可以通过转化得到其他问题的高效算法.因而前一类目的的研究已经显著降温,后一类目的的研究则更有实用价值.这就是NP完全问题的意义和实质.关于NP完全问题,还有一个重要概念就是伪多项式时间算法.举例来讲,整数背包问题：给定一些整数C j,j＝1,2, n,以及整数b,是否存在整数X1, X n＞＝0使得n j＝1ðC j X j＝b？该问题是经典的NP完全问题,但该问题存在针对参数n和b的多项式时间算法,称伪多项式时间算法.也就是说,必须限定b的大小为n的多项式,该问题才具有多项式时间算法.而当b很大,为n的指数幂时,按同样方法得到的算法的时间复杂度就不是多项式,而是指数型了.一些研究者不理解这一点,花了大量的时间和精力,找到了该问题的在限定了b的大小的前提下的多项式时间算法,就真的以为已经解决了NP是否等于P的问题.其实是大谬误. 2关于NP完全问题时间复杂度的争论首先讨论NP完全问题时间复杂度的一些特点.一般来说,对于所熟悉的许多多项式时间问题,其时间复杂度的曲线很光滑.也就是说,局部范围的输入数据,往往具有整体时间复杂度的特性.例如,对于著名的冒泡排序算法,其时间复杂度在最坏的情况下是n的平方,在最快的情况下为常数,平均时间为二分之n的平方,且其分布呈光滑的曲线,并且这样的曲线很容易通过算例描绘出来.在n等于任何值的时候,都具有这样的特点. NP完全问题,比如哈密尔顿环,就完全不是这样了.哈密尔顿环的特点是：对一个不大的n,其可能的算例数量极其庞大,且这些算例的难易程度分布相当复杂,没有规律,现在还没有人能掌握这些算例难易程度的分布规律.例如,国际某网站有关于最难算的哈密尔顿的算例,这些算例用笔者的程序可以非常轻松和快速地解决.因而,对于某个NP完全问题,一个计算程序所说在最坏情况下的计算时间,只能指的是在所算的例子中最慢的那一个,而不是指：该程序找到了这样的例子,它代表了此问题计算时间复杂度的上限.这样的例子是没有人能找得到的,而冒泡排序之类的多项式问题则非常容易找到这样的例子,且呈固定的概率分布.故而对NP完全问题算法的思维不能停留在对一些简单问题的思维层面上.就算真的能找到在最坏情况下的问题,也不能排除在客观世界存在有这样的NP完全问题,比如：它的时间复杂度上限是某个值,但在某个数据段,最坏的情况的复杂度是另一个值,在另一个数据段最坏的情况又是一个不同的值,等等.这就是为什么NP完全问题时间复杂度难以确定的根本原因.自从史蒂文库克论证了NP完全问题的存在, NP是否等于P随即开始困扰人类,考量着人类复杂的思路能力和计算能力.此问题也很快被公认为最具挑战性的世界难题.如果能证明某个NP完全问题存在多项式时间算法,即可判定所有NP问题都具有多项式时间算法.如前所述,迄今已发现4千多个NP完全问题,还没有人能论证完全问题学者具有多项式时间算法,也没有人能否定其具有多项式时间算法.相关领域的学者往往根据自己的感觉或倾向拥有自己的判断,这些判断不能说是科学的或有实际价值的.有人对一些数学家和计算机科学家做过统计,结果大多数倾向于认为NP不等于P,只有小部分认为两者相等.一些科学家在提出NP不等于P的判断时,所举的理由仅仅是泛泛的,而不具备严格的科学认证价值.举例如下：一个算法学家,在一本算法专著上写到：迄今已出现了大量NP完全问题,由于许多最优秀的算法专家和数学家在长期研究这些问题,却没有找到一个多项式算法,故倾向于判断NP不等于P[1]. ACM期刊主编是这样论证NP不等于P的：若谁证明了NP等于P,则他不仅只是解决了NP问题,所有7大世纪难题他都解决了,因为所有科学研究问题的解决都属NP[7].还有专家认为：由于非确定性图灵机的计算能力明显强于确定性图灵机,从而NP不等于P.当然,也有不少专家认为NP等于P.下面给出NP是否等于P的一些启发式思考. 3科研问题的解决与NP完全问题NP问题为何如此具有影响力？其原因一是问杜立智,等：NP完全问题研究及前景剖析75武汉工程大学学报第37卷题本身确实难解,极具挑战性,二是,它考量人类思维能力和计算能力的极限.人的思维是串行的而不具备并行思维能力,而所有科学问题的解决途径,其实都是NP.若是NP等于P,则理论上,只具有串行思维能力的人类,可以解决所有科学难题.而若是NP 不等于P,也就是大量的NP问题会是指数型的,则不幸得很,大量科学问题人类思维很难解决.因为指数型通常意味着2的n次方或更大,当n的规模达到小小的100时,解决问题所需的思维步骤将达100万亿亿亿步,这是人类思维能力所无法企及的,哪怕花上万万年的时间.从哲学上可以这么说,是否赞成NP等于P,是区分可知论和不可知论的分水岭.公认为20世纪最伟大的数学家的希尔伯特有句名言：我们必须知道,我们必能知道！可见,本质上,希尔伯特是赞成NP等于P的！而他在20世纪刚开始所提出的23个高不可攀的数学问题,也已经陆续得到了解决,仿佛是在证明他的 我们必能知道 的断言.人类历史上,一个个科学难题在不断被解决,难道不是在印证着NP等于P吗？笔者对此的质疑逻辑是：如前所述,所有科研难题的解决途径是NP,因而NP是否等于P这一难题的解决途径无疑也属NP.鉴于这是科学难题,许多科学家判断,该问题人类长时期很难解决,例如上述ACM的期刊主编就是这样判断的,因而有理由认为该问题属于NP难,并且其解决过程所包含的参量也就是n不可能很小.这意味着任何宣称证明了NP不等于P的人,其实是在用自己证明的结论,去否决自己证明的可能性和正确性,也就是说,是在循环否定.4围棋软件开发与NP完全问题曾有人提议,若能开发一个围棋软件,能打败所有围棋高手,也就是说其思路已达到最优,那不就一切都证明了吗？此提议非常好,但要做好还有诸多困难,而且就算做好了,也不意味NP问题的解决.下围棋属敌对搜索,是极大极小搜索加剪枝问题中的一种.问题在于,它的分支数非常大,也就是可选的点很多,因而计算深度就只能很浅了,否则计算量和储存量都会大得惊人.不仅如此,它的状态值量化非常困难,从而在进行优劣选择以及剪枝时,非常难以把握.因此,迄今最好的围棋软件只能达到业余二段的水平,与专业高段棋手比当然是相差甚远.人下围棋能达到专业强九段的水平,不妨假定此水平极高.由此就产生了如下问题：（1）围棋是NP吗？（2）围棋是NPC吗？（3）此问题能在多项式内解决吗？注意到强九段,显然,不能认为强九段的思维能力和记忆能力能满足指数型.不妨设想人类能出现这样顶级的围棋高手,他下棋就能达到最优,也就是说能在多项式时间内完成判断计算.这就意味着,一个明显的指数型搜索问题,有人却可在多项式内完成.这是如何办到的呢？回答只能是：在充分研究后,加上充分的知识积累以及复杂的关联信息的充分把握.从逻辑上可以判断,人能做到的,软件也应能做到,且不会增加计算量和储存量.对这个问题的分析,可以得到解决NP完全问题的某些启发.此外,近年来一些论文提到的一些研究技巧,亦对NP问题的研究有所助益[8-10].针对Hamilton环这一NP完全问题的多项式时间算法的研究尝试也一直在进行[11].多年来,笔者也坚持进行该问题的研究,已经有相当乐观的结果.5个体和群体及概率与NP完全问题同样,从启发思维的角度,如前所述,至今已发现了4000多个NP完全问题,且还会继续发现.由于任何一个NP完全问题,都可以多项式规约到另一个任意的NP完全问题,也就是说,所有NP 完全问题两两之间的距离是多项式,这件事实本身强烈地昭示着（strongly imply）,NP问题具有统一的求解规律和难解度,并且也应具有多项式量级.客观世界的任何一个群体,其任意个体之间某个属性的差值,与个体属性的绝对值通常都处在同一个量级.举例说来：通常成人的体重是百斤量级,很肥壮和很瘦的人之间体重的差值也是百斤量级.同样,很肥大的蚂蚁与很瘦小的蚂蚁体重之差值也与通常单个成年蚂蚁的体重处在同一个数量级.再举一个例子：假使在某个太空中随机选n个点,n显著大于1,若其中任两个点之间的距离都不超过1010米,就有理由认为,该太空本身的最大尺76第10期度也在1010米量级.不难看出,这些问题之间具有相同的内在逻辑,从而也给人们在NP完全问题的认识上以启发. 6结语NP完全问题的相关概念十分的抽象,难以把握,无论学生或研究人员,常有相关问题的概念错误或理解模糊,本文用通俗的语言揭示了这些概念的本质.在NP完全问题的研究中,最为关键的是正确的研究方向,若是研究方向为并不成立的谬误所误导,则不仅会导致多走弯路,甚至可能是完全做无用功.其中一个最大的谬误就是,认为NP当然的不等于P.这就意味着所有NP完全问题不可能有多项式时间算法,因此从根本上限制了这方面的研究.许多学者包括一些专家都将其作为限制框框.这仅仅只是一些研究人员的一种个人倾向,而绝不是定论.有理由认为其有可能甚至极可能是错的.还有一种倾向就是将P vs.NP问题过分神秘化,要么宣称该问题不能在人类已有知识框架内解决,要么宣称今后很长时期人类不可能解决.所有这些宣称并无切实的依据.本文详细论述了NP完全问题的实质,并从多个角度,用启发式思维方式,分析了其时间复杂度及其特性,以及可行的研究前景和研究方向.可供相关领域的学者参考.致谢感谢湖北省自然科学基金对本研究的支持！参考文献：[1]ARORA S,BARAK plexity Theory：A Mod-ern Approach Cambridge University Press[M].Cam-bridge,2009[2]AARONSON S.Is P versus NP formally independent[J].Bulletin of the European Association for Theoreti-cal Computer Science,2003,81（10）：109-136.[3]杜丁柱,葛可一,王洁.计算复杂性导引[M].北京：高等教育出版社,2002：35-57.DU ing-zhu,Ge Keyi,Wang Jie.Introduction to Com-puting Complexity[M].Peking：High Education Press,2002：35-57.（in Chinese）[4]SARTAJ Sahni,Data Structures,Algorithms,and Appli-cations in C＋＋[M].McGraw-Hill,1998. [5]COOK S A.The complexity of theorem proving proce-dures[M].Proceedings of Third Annual ACM Sympo-sium,New York：on Theory of Computing,Associationfor Computing Machinery,1971：151-158. [6]KARP R M.Reducibility among combinatorial problems[M].Miller R E,Thatcher J W Plenum Press,Com-plexity of Computer Computations,New York：1972：85-104.[7]LANCE Fortnow.The Status of the P Versus NP Prob-lem[J].Communications of the ACM,2010,52（9）：78-86.[8]朱丽君,陈金芳.大数据下中文期刊论文被引分析[J].武汉工程大学学报,2015,37（5）：74-78.ZHU Li-jun,CHEN Jin-fang.Citation analysis on Chi-nese Periodicals Under big data[J].Journal of WuhanInstitute of Technology,2015,37（5）：74-78.（in Chi-nese）[9]付敏,戴祖旭,王道蓬.压缩编码的上下文树构造算法[J].武汉工程大学学报,2015,37（4）：51-55.Fu Min,Dai Zuxue,WANG Dao-peng.Context tree al-gorithm based on compression encoding[J].Journal ofWuhan Institute of Technology,2015,37（4）：51-55.（inChinese）[10]殷秀叶.大数据环境下的相似重复记录检测方法[J].武汉工程大学学报,2014,36（9）：66-69.YIN Xiu ye.Method for detecting approximately dupli-cate database records in big data environment[J].Journal of Wuhan Institute of Technology,2014（9）：66-69.（in Chinese）[11]POSA L.Hamiltonian circuits in random graphs[J].Discrete Math,1976（14）：359-364.杜立智,等：NP完全问题研究及前景剖析7778武汉工程大学学报第37卷NP-complete problem and its futureDU Li-zhi，CHEN He-ping，FU Hai-dOngCollege of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan430065,ChinaAbstract：P versus NP is one of the most important problems in theoretical computer science.Because the concepts about it are very abstract and complicated,some scholars and students in computer science often misunderstand them.A lot of published papers contain these misunderstandings.The main problems are：the defaults in understanding the concepts of NP and NPC,unclearly understanding the concepts of deterministic turing machine and non-deterministic turing machine,misreading the relationship of P and NP and mislead-ing in the study direction of NP,etc.Of all these concepts,the core concept is the NP-complete problem.In this paper,we analyzed the misunderstandings.By deeply studying the definitions,we revealed their essence. Specially,by analyzing a lot of questions in different fields,we gave some heuristic strain of thoughts for the possible ways to solve the NP-complete problem and the possible directions to study it.Keywords：deterministic turing machine；nondeterministic turing machine；NP-complete problem本文编辑：陈小平NP完全问题研究及前景剖析作者：杜立智， 陈和平， 符海东， DU Li-zhi， CHEN He-ping， FU Hai-dong作者单位：武汉科技大学计算机科学与技术学院,湖北 武汉,430065刊名：武汉工程大学学报英文刊名：Journal of Wuhan Institute of Technology年，卷(期)：2015,37(10)引用本文格式：杜立智.陈和平.符海东.DU Li-zhi.CHEN He-ping.FU Hai-dong NP完全问题研究及前景剖析[期刊论文]-武汉工程大学学报 2015(10)。
10 NP-完全问题
多项式界与P类问题
一、多项式（时间）界 区分难解问题与易解问题的界限就是多项式（时间）界。 计算复杂性理论的两个基本论题： Church-Turing 论题 Cook-Karp 论题 Church-Turing论题利用Turing机指出了那些问题是可计算的， 这个“可计算的”问题类非常大，几乎所有的问题都是可计算的， 反例不多。 Cook-Karp论题则是：在可计算的问题（函数）中，只有在多 项式阶时间内可计算的问题才是实际可计算的，称为该计算是可行 的或该问题是易解的。这个易解问题类就称为P类，是可计算问题 类的一个很小的子集。
合取范式的可满足性问题：是否有一组对所有命题变量的赋值 （F或T)，使得整个CNF取值为真（T）。
一些难解问题
（6）图的团集问题
图G=<V,E>的团集，是指G的一个完全子图，即该子图中任意两 个互异的顶点都有一条边相连。 无向图G=<V,E>的团集问题：求G的最大子团。
v2 v3
v1
v4
v5
一些难解问题
带罚款的作业调度问题：求一种调度方案，即求{1,2,…,n} 的一种排列，使得按这种顺序完成n项作业所付出的罚款数最小。
一些难解问题
（5）可满足性问题
这个问题也称合取范式的可满足问题。 一个合取范式形如：A1∧A2∧…∧An（即若干子句的逻辑乘） 子句Ai形如：a1∨a2∨…∨ak,其中aj(1<=j<=k)为某一布尔变 量或是该变量的非。
T4(n)＝2n 0.001秒 4×1016年
多项式界与P类问题
（4）从理论上来说，多项式具有两个性质： “闭包”性质：许多实际问题是一些子问题的组合或重叠。 而多项式函数通过算术运算的组合或重叠（即多项式函数的多项式 函数），得到的仍然是多项式界的。 不同计算模型的“独立”性或不依赖性：即某一问题在一种 计算模型（如Turing机）下有多项式算法，那么它一定也在其它几 种模型下有多项式算法。
4.4 一些NP完全问题
2010-7-30
21
21.瓶颈上的巡回推销员:m个城市的集合C对 21.瓶颈上的巡回推销员: 于每一对城市ci,cj∈C,有距离d(ci,cj)∈Z+, 正整数B. 问:是否有C上的巡回旅行路线,其中最长的 边的长度不大于B,即是否有C的一个排列 <cπ(1), cπ(2),…cπ(m)>, 使得对于l≤i≤m,有d (cπ(i), cπ(i+1))≤B, 并且d (cπ(m), cπ(1))≤B ? 注释:即使对于所有的ci,cj∈C,有 d(ci,cj)∈{1,2},也还是NP完全的.
2010-7-30
23
23.乡村邮递员: 23.乡村邮递员:图G=(V,E),每条边长度为 l (e) ∈ Z + 0 +. 子集E'∈E,界B∈Z 问:G中是否有一条回路包含E'中的每一条边, 并且总长度不趟过B? 注释:即使对于所有e∈E有l(e)=1,仍然是NP 完全的,关于有向图的对应的问题也是如此.
2010-7-30
3
3.三角划分:图G=(V,E),且|V|=3q,q是某 三角划分: 个整数. 问:G的顶点是否能被划分成q个不相交的集合 V1,V2,…,Vq, 其中每个集合恰好包含有三个顶点,使得对于 每个Vi={ui,vi,wi},1≤i≤q,三条边{ui,vi,}, {ui,wi}{vi,wi},都属于E?
5
5.独立集:图G=(V,E),正整数K≤|V|. 独立集: 问:G是否会有大于等于K的独立集,即是否有 子集 V'V 使得|V'|≥K并且V'中的任意两个顶点都不被E 中的边所连接?
2010-7-30
6
6.单连通子图:有向图G=(V,A),正整数 单连通子图: K≤|A|. 问:是否有子集A'A,|A'|≥K,使得 G'=(V,A')在任意一对顶点之间至多只有一条有 向通路? 注释:对于无圈有向图仍然是NP完全的.
算法设计技巧与分析：第九讲 NP完全问题
• 最优化问题: MAX-CLIQUE.
输入：一个无向图G=(V,E). 输出:一个正整数k，它是G中最大团集的大小
Algorithms Design Techniques and Analysis
• 如果我们有一个求解判定问题的有效算法，那么很容易把 它变成求解与它相对应的最优化问题的算法。 • 例如，我们有一个求解图着色判定问题的算法A，则可以 用二分搜索并且把算法A作为子程序来找出图G的色数。 很清楚，1<=x (G)<=n，这里n是G中顶点数，因此仅用 O(1og n)次调用算法A就可以找到G的色数。由于我们正处 理多项式时间的算法， log n因子是不重要的。
• 定理 10.1
• P类问题在补运算下是封闭的。
Algorithms Design Techniques and Analysis
Algorithms Design Techniques and Analysis
例子 10.3
给出一个无向图G=(V,E)，对于某个正整数k, G中大 小为k的团集，是指G中有k个顶点的一个完全子图。 团集问题是问一个无向图是否包含一个预定大小的 团集。 • 判定问题: CLIQUE.
输入:一个无向图G=(V,E)和一个正整数k。 问题: G有大小为k的团集吗?
Algorithms Design Techniques and Analysis
P类的问题
• 2着色问题: • 给出一个无向图G ，它是否是2可着色的?即它的顶点是否可仅用 两种颜色着色，使两个邻接顶点不会分配相同的颜色?注意，当且 仅当G是二分图，即当且仅当它不包含奇数长的回路时，它是2可 着色的。
2.47×1041 1024
观察结论：n≤100时，（不自然的）多项式函数值大于指数 函数值，但n充分大时，指数函数仍然超过多项式函数。
NP-完全问题：一些典型的例子
P-Polynomial (time)
算法复杂性
Computable
Polynomial time is assumed the lowest complexity
Complete
Reducible
变换/封闭性
NP-完全问题：一些典型的例子
NP-C:典型的问题（1）
问题1 图着色问题
判定问题：是否存在不超过k种颜色的着色方案? 优化问题：求图的最小着色数和着色方案
NP-完全问题：一些典型的例子
Problems-unknown in NP
Kth重子集问题:任给定n+2 个正整数 c1,┅cn, k, L; 是 否存在{1,2,┅,n} 的k 个不同子集S1,┅Sk 使得对所有 i=1,┅,k 有
cj L
jSi
Σ部分称为子集的重量, 重量排序第k的子集. 当k=2n-1时,表示可行解的字符串的长度有指数的长度.
该可行调度的执行时间ti之和≤C(可行性) 又因ti=pi=si,所以该可行调度对应罚款额=S-Σpi =S-Σti≥S-
C=k 所以其罚款额＝k，而且被调度的作业的时间之和＝C
NP-完全问题：一些典型的例子
NP-难度和NP-完全问题
问题Q是NP-难度问题，如果：
每个NP问题都可多项式地约化为问题 Q.
我们不知道该问题是否在NP中. 图G的最大集团的节点数是否=k? 上述问题是否在
NP?也是未知的! (验证最大集团,不能在多项式时间内 做到)
NP-完全问题：一些典型的例子
CNF-satisfiablity问题是NP-完全问题
定理13.5 CNF-satisfiablity问题是NP-完全问题 这是著名的Cook定理 Cook 定理的推论:如果CNF-可满足问题有多
第10章 NP完全问题(自己写的)
如果对于任意的问题C，II的补也在C中， 我们就说问题II属于C在补运算下是封闭的。 例如： 2着色问题的补可以陈述如下： 给出一个图G，它是不2着色的吗？ 上述问题属于P类证明： 存在一个确定算法A，当对于2可着色时， 它停机说：yes；在计算not-2着色时，它停机 说no。 对算法A进行简单的交换yes或no,可以得 出no-2算法是一个确定性算法。
• 推论10.1： 如果II和II'是NP中的两个问题，若存在II' 可以规约到II，并且II'是NP完全的，则II是NP 完全的。 证明：因为II'是NP完全的，NP中的每一 个问题在多项式时间内可以规约到II'。因为II' 可以规约到II，所有由上述定理知道： NP中的每一个问题在多项式时间可以规约 到II，就可以知道II是NP完全的。
二、P类 定义10.1：设A是求解问题II的一个算法， 如果在展示问题II的一个实例时，在整个执行 过程中每一步都只有一个解，则成算法A是确 定性算法。因此，如果对于同样的输入，实 例多次执行，其输出不会改变。 例如：求解ax2+bx+c=0； 定义10.2： 判定问题的P类由这样的判定 问题组成,ห้องสมุดไป่ตู้们的yes/no解可以用确定性算法 在运行多项式步数内得到。（例如：O(nk)）
• 证明NP问题的思路： （1）II在NP中； （2）存在一个NP完全问题II'，使得II'可以规 约到II。 例子：哈密顿回路问题和旅行商问题。 （1）哈密顿回路：给出一个无向图G=(V,E)， 它有哈密顿回路吗？即：一条恰好访问每一个 顶点一次的回路。 （2）旅行商问题：给出一个n个城市集合， 且给出城市间的距离。对于一个整数k,是否存 在最长的为k的游程？这里一条游程就是一个 回路，他恰好访问每一个城市一次。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第10章 NP完全问题
主讲：王培崇
对一个已确定是可计算的问题，人们总试图寻求实现它的最优算法。然而 对有些问题，这个工作难度很大，目前还不能做到这点。
1、P类问题：问题的时间复杂性是多项式阶的，这只须设 计一个实现它的时间复杂性是多项式阶的算法即可，例如分类 （又称排序）问题。 2、顽型问题：人们已经设计出实现它的时间复杂性为指数阶 的算法，并且已证明该问题不存在多项式阶的算法，例如梵塔 问题；但是有这样一类问题， 3、NP问题：人们目前已设计的实现它的算法其时间复杂性 为指数阶的，但还不能肯定它有或没有多项式阶的算法。
如果是，则停机回答yes，如果不是则停 机回答no。
（上述是以图灵机计算模型实现的。）
• 定义10.3
NP类问题由下面的判定问题组成，对 于它们存在着多项式时间内运行的不确定性 算法。
例子10.4
coloring问题：
（1）设I是coloring的一个实例，s宣称是I的 解。容易建立一个确定性算法验证s选择、送餐车辆指派问题、车 间调度问题等。
见表1.1，现存的求解方法，中等输入也 需要几百年时间才能求解成功。
4、NP问题的描述转换 转换为判定问题。
两种答案：yes或no。 最优化问题：关心的是某个量的最大化或 最小化问题。
5、问题转化举例： 10.1设s是一个实数序列，EU问题是：是否S 中的所有的数都不相同。
判定问题：
输入：一个整数序列S； 问题：在S中存在两个数据相等吗。 10.2 给出一个无向图G=(V,E)，用k种颜色对G 着色.......，使得图中没有两个邻接点有相同的 颜色。
• 判定问题： 输入：一个无向图G=(V,E)和一个正整数k>=1； 问题：G可以k着色吗？即G最多可以用k种颜 色着色吗？
可以得出结论该问题属于NP类。
（2）建立不确定算法 对图G进行编码表示，建立并运行下面的算法A。 a、首先对于顶点集合产生一个任意颜色的指派， 猜测一个解。 b、验证该解是否合适的有效指派。 c、该解有效，停机回答yes；否则，停机回答no。
NP类与P类的区别： （1）P是一个判定问题类，这些问题可以用一个确 定性算法在多项式时间内判定或解出； （2）NP是一个判定类，这些问题可以用一个确定 性算法在多项式时间内检查或验证他们的解。
例如：求解ax2+bx+c=0；
定义10.2： 判定问题的P类由这样的判定 问题组成,他们的yes/no解可以用确定性算法 在运行多项式步数内得到。（例如：O(nk)）
• 下面问题的解都是P类问题：
1、排序问题：给出一个n个整数的表，他们 能否按非降序排列；
2、不相交集问题：给出两个整数集合，他们 的交集是否为空？
这些问题，目前根本没有找到有效解方式。（在 可以容忍的时间内解决问题。）
这些问题目前被认为是难解的。（没有确定解公 式），以后也不可能找到确定解公式。
这些难解问题，目前的求解规模在2n或n!。
• 3、这一类问题的相通性： 数百个著名的问题。
有趣的是，如果其中一个能够找到多项式 可解，那其他的问题都可以找到多项式解。
NP完全理论还很年轻，有许多问题等待人们研究。例如， “NP＝P”还是相反“P是NP的真子集”。这个问题是当代计算 机科学中的一大难题。
• 一、序言
1、 观察：前面提到的各种排序算法、图遍历算法 等，动态规划解背包等。
上述各种算法的复杂度都是在低阶多项式级别下 完成的。
2、有另外一类问题：m-图着色问题（m>2）、生 产车间调度问题、最短路径（路由）、神经网络参数 优化问题等。
如果断言解导致答案是yes，就存在一种 方法可以在多项式时间内验证这个解。
• 非确定性算法：
（1）猜测阶段：产生一个任意字符解串， 可能对应一个实例解，也可能不是。但是要 求在多项式步数内产生。
（2）验证阶段：
首先检查该字符解串，是不是合适的形 式，如果不是，停机回答no；如果是合适的 形式，则继续检查它是不是问题的实例x的解。
3、最短路径：在一个有向图G=(V,E)中，两 个特异的顶点s，t和一个整数k，在s和t之间 是否存在一条路径，它的长度最多是k。
4、2着色问题：给出一个无向图G，问它是 否可以用两种颜色着色。
如果对于任意的问题C，II的补也在C中， 我们就说问题II属于C在补运算下是封闭的。
例如：
2着色问题的补可以陈述如下：
最优化问题：求出G的着色数。 输入：一个无向图G=(V,E) 输出：G的色数。 研究NP难问题，将精力更多的投入到研 究判定问题的求解方面。
二、P类
定义10.1：设A是求解问题II的一个算法， 如果在展示问题II的一个实例时，在整个执行 过程中每一步都只有一个解，则成算法A是确 定性算法。因此，如果对于同样的输入，实 例多次执行，其输出不会改变。
1971年S. Cook发表了“The Complexity of Theorem Proving Procedures”这篇著名论文，1972年R. Karp发表了 “Reducibilty Among Combinatorial Prob1ems”，从此奠 定了NP完全理论的基础。NP完全理论指出在NP类中有一些问 题具有以下性质：若其中一个问题获得多项式算法，则这一类 问题就全部获得了多项式算法；反之，若能证明其中一个问题 是多项式时间内不可解的，则这-类问题就全部是多项式时间内 不可解的。这类问题将称之为NP完全问题。NP完全理论不打算 找出这一类问题的算法，仅仅着眼于证明这一类问题的等价性 ，即证明它们的难度相当。
给出一个图G，它是不2着色的吗？
上述问题属于P类证明：
存在一个确定算法A，当对于2可着色时， 它停机说：yes；在计算not-2着色时，它停机 说no。
对算法A进行简单的交换yes或no,可以得 出no-2算法是一个确定性算法。
三、NP类
非形式化概念：
NP类问题由这样的问题II组成，对于这 些问题存在一个确定性算法A，该算法在对II 的一个实例展示一个断言解时，它能在多项 式时间内验证解的正确性。
主讲：王培崇
对一个已确定是可计算的问题，人们总试图寻求实现它的最优算法。然而 对有些问题，这个工作难度很大，目前还不能做到这点。
1、P类问题：问题的时间复杂性是多项式阶的，这只须设 计一个实现它的时间复杂性是多项式阶的算法即可，例如分类 （又称排序）问题。 2、顽型问题：人们已经设计出实现它的时间复杂性为指数阶 的算法，并且已证明该问题不存在多项式阶的算法，例如梵塔 问题；但是有这样一类问题， 3、NP问题：人们目前已设计的实现它的算法其时间复杂性 为指数阶的，但还不能肯定它有或没有多项式阶的算法。
如果是，则停机回答yes，如果不是则停 机回答no。
（上述是以图灵机计算模型实现的。）
• 定义10.3
NP类问题由下面的判定问题组成，对 于它们存在着多项式时间内运行的不确定性 算法。
例子10.4
coloring问题：
（1）设I是coloring的一个实例，s宣称是I的 解。容易建立一个确定性算法验证s选择、送餐车辆指派问题、车 间调度问题等。
见表1.1，现存的求解方法，中等输入也 需要几百年时间才能求解成功。
4、NP问题的描述转换 转换为判定问题。
两种答案：yes或no。 最优化问题：关心的是某个量的最大化或 最小化问题。
5、问题转化举例： 10.1设s是一个实数序列，EU问题是：是否S 中的所有的数都不相同。
判定问题：
输入：一个整数序列S； 问题：在S中存在两个数据相等吗。 10.2 给出一个无向图G=(V,E)，用k种颜色对G 着色.......，使得图中没有两个邻接点有相同的 颜色。
• 判定问题： 输入：一个无向图G=(V,E)和一个正整数k>=1； 问题：G可以k着色吗？即G最多可以用k种颜 色着色吗？
可以得出结论该问题属于NP类。
（2）建立不确定算法 对图G进行编码表示，建立并运行下面的算法A。 a、首先对于顶点集合产生一个任意颜色的指派， 猜测一个解。 b、验证该解是否合适的有效指派。 c、该解有效，停机回答yes；否则，停机回答no。
NP类与P类的区别： （1）P是一个判定问题类，这些问题可以用一个确 定性算法在多项式时间内判定或解出； （2）NP是一个判定类，这些问题可以用一个确定 性算法在多项式时间内检查或验证他们的解。
例如：求解ax2+bx+c=0；
定义10.2： 判定问题的P类由这样的判定 问题组成,他们的yes/no解可以用确定性算法 在运行多项式步数内得到。（例如：O(nk)）
• 下面问题的解都是P类问题：
1、排序问题：给出一个n个整数的表，他们 能否按非降序排列；
2、不相交集问题：给出两个整数集合，他们 的交集是否为空？
这些问题，目前根本没有找到有效解方式。（在 可以容忍的时间内解决问题。）
这些问题目前被认为是难解的。（没有确定解公 式），以后也不可能找到确定解公式。
这些难解问题，目前的求解规模在2n或n!。
• 3、这一类问题的相通性： 数百个著名的问题。
有趣的是，如果其中一个能够找到多项式 可解，那其他的问题都可以找到多项式解。
NP完全理论还很年轻，有许多问题等待人们研究。例如， “NP＝P”还是相反“P是NP的真子集”。这个问题是当代计算 机科学中的一大难题。
• 一、序言
1、 观察：前面提到的各种排序算法、图遍历算法 等，动态规划解背包等。
上述各种算法的复杂度都是在低阶多项式级别下 完成的。
2、有另外一类问题：m-图着色问题（m>2）、生 产车间调度问题、最短路径（路由）、神经网络参数 优化问题等。
如果断言解导致答案是yes，就存在一种 方法可以在多项式时间内验证这个解。
• 非确定性算法：
（1）猜测阶段：产生一个任意字符解串， 可能对应一个实例解，也可能不是。但是要 求在多项式步数内产生。
（2）验证阶段：
首先检查该字符解串，是不是合适的形 式，如果不是，停机回答no；如果是合适的 形式，则继续检查它是不是问题的实例x的解。
3、最短路径：在一个有向图G=(V,E)中，两 个特异的顶点s，t和一个整数k，在s和t之间 是否存在一条路径，它的长度最多是k。
4、2着色问题：给出一个无向图G，问它是 否可以用两种颜色着色。
如果对于任意的问题C，II的补也在C中， 我们就说问题II属于C在补运算下是封闭的。
例如：
2着色问题的补可以陈述如下：
最优化问题：求出G的着色数。 输入：一个无向图G=(V,E) 输出：G的色数。 研究NP难问题，将精力更多的投入到研 究判定问题的求解方面。
二、P类
定义10.1：设A是求解问题II的一个算法， 如果在展示问题II的一个实例时，在整个执行 过程中每一步都只有一个解，则成算法A是确 定性算法。因此，如果对于同样的输入，实 例多次执行，其输出不会改变。
1971年S. Cook发表了“The Complexity of Theorem Proving Procedures”这篇著名论文，1972年R. Karp发表了 “Reducibilty Among Combinatorial Prob1ems”，从此奠 定了NP完全理论的基础。NP完全理论指出在NP类中有一些问 题具有以下性质：若其中一个问题获得多项式算法，则这一类 问题就全部获得了多项式算法；反之，若能证明其中一个问题 是多项式时间内不可解的，则这-类问题就全部是多项式时间内 不可解的。这类问题将称之为NP完全问题。NP完全理论不打算 找出这一类问题的算法，仅仅着眼于证明这一类问题的等价性 ，即证明它们的难度相当。
给出一个图G，它是不2着色的吗？
上述问题属于P类证明：
存在一个确定算法A，当对于2可着色时， 它停机说：yes；在计算not-2着色时，它停机 说no。
对算法A进行简单的交换yes或no,可以得 出no-2算法是一个确定性算法。
三、NP类
非形式化概念：
NP类问题由这样的问题II组成，对于这 些问题存在一个确定性算法A，该算法在对II 的一个实例展示一个断言解时，它能在多项 式时间内验证解的正确性。