第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)。
取其最⾼次，可以看出，这是⼀个时间复杂度为多项式的表⽰⽅式。
- 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 的一个实例展示一个断言解时，它能在多项 式时间内验证解的正确性。