1、 第第8 8课课 计算复杂性计算复杂性第第3 3章章 计算复杂性与智能算法计算复杂性与智能算法 第第8 8课课 计算复杂性计算复杂性 第第9 9课课 近似算法近似算法 第第1010课课 智能型算法智能型算法 第第1111课课 线性规划线性规划 第第8 8课课 计算复杂性计算复杂性第第8 8课课 计算复杂性计算复杂性 算法复杂性问题算法复杂性问题 图灵机图灵机 P P类与类与NPNP类问题类问题 NPNP完全问题完全问题 第第8 8课课 计算复杂性计算复杂性 算法的复杂性问题算法的复杂性问题 算法本身能不能解，这个问题应该在求解问算法本身能不能解，这个问题应该在求解问题前就应该首先确定，因为如果
2、一个问题是题前就应该首先确定，因为如果一个问题是不可解的，那么对这个问题寻求算法的努力不可解的，那么对这个问题寻求算法的努力也是徒劳的。问题否可解的相关内容，也就也是徒劳的。问题否可解的相关内容，也就是算法复杂性理论所涉及到的内容。包括是算法复杂性理论所涉及到的内容。包括P P、NPNP问题的定义以及比较，还有确定型图灵机问题的定义以及比较，还有确定型图灵机的介绍。这些内容不足以构成算法复杂性理的介绍。这些内容不足以构成算法复杂性理论体系，但是了解这些内容是复杂性理论深论体系，但是了解这些内容是复杂性理论深入学习的基础。入学习的基础。计算复杂性问题计算复杂性问题 第第8 8课课 计算复杂性计算
3、复杂性 可解问题与不可解问题可解问题与不可解问题 并不是任何计算问题都能够利用计算机来解并不是任何计算问题都能够利用计算机来解决。算法复杂性理论关心的是哪些问题是可决。算法复杂性理论关心的是哪些问题是可以利用计算机来解决的，也就是说是以利用计算机来解决的，也就是说是“可解可解的问题的问题”；哪些问题是在计算机也解决不了；哪些问题是在计算机也解决不了的，也就是的，也就是“不可解的问题不可解的问题”。尽管理论上。尽管理论上可解的问题在实际中未必能够找到实现的算可解的问题在实际中未必能够找到实现的算法，但算法复杂性理论关心的是如何在理论法，但算法复杂性理论关心的是如何在理论上证明问题的可解，而不关心
4、具体如何实现上证明问题的可解，而不关心具体如何实现。计算复杂性问题计算复杂性问题 第第8 8课课 计算复杂性计算复杂性 P P问题与问题与NPNP问题问题 如果一个判定性问题的复杂度是该问题如果一个判定性问题的复杂度是该问题的一个实例的规模的一个实例的规模n n的多项式函数，则我们说的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题这种可以在多项式时间内解决的判定性问题属于属于P P类问题。类问题。P P类问题就是所有复杂度为多类问题就是所有复杂度为多项式时间的问题的集合。通俗地称所有复杂项式时间的问题的集合。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否度为多项式时间的问题
5、为易解的问题类，否则为难解的问题。则为难解的问题。这种可以在多项式时间内验证一个解是否正这种可以在多项式时间内验证一个解是否正确的问题称为确的问题称为NPNP问题问题,亦称为易验证问题类。亦称为易验证问题类。计算复杂性问题计算复杂性问题 第第8 8课课 计算复杂性计算复杂性 NPNP理论的核心问题理论的核心问题 如果说如果说P P问题是问题是NPNP问题的一个真子集，问题的一个真子集，那么可以不必花太多时间寻找大规模输入那么可以不必花太多时间寻找大规模输入NPNP问题的解，因为这样的努力都是徒劳的；然问题的解，因为这样的努力都是徒劳的；然而如果能够证明而如果能够证明NPNP问题是问题是P P问
6、题，那么结果就问题，那么结果就很不一样了，它说明了现在许多的指数复杂很不一样了，它说明了现在许多的指数复杂度的问题都有多项式复杂度的解法，只不过度的问题都有多项式复杂度的解法，只不过是暂时找不到而已。是暂时找不到而已。计算复杂性问题计算复杂性问题 第第8 8课课 计算复杂性计算复杂性 三种常用计算模型三种常用计算模型.随机存取机随机存取机RAMRAM模型模型.随机存取存储程序机随机存取存储程序机RASPRASP模型模型.图灵机模型图灵机模型 计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性随机存取机随机存取机RAMRAM1.1.RAMRAM的结构的结构 计算复杂性计算复杂性问
7、题问题 第第8 8课课 计算复杂性计算复杂性2.2.RAMRAM程序程序 一个一个RAM程序定义了从输入带到输程序定义了从输入带到输出带的一个映射。可以对这种映射关系出带的一个映射。可以对这种映射关系作作2 2种不同的解释。种不同的解释。解释一：解释一：把把RAMRAM程序看成是计算一个函数程序看成是计算一个函数若一个若一个RAMRAM程序程序P P总是从输入带前总是从输入带前n n个个方格中读入方格中读入n n个整数个整数x x1 1，x x2 2，x xn n，并并且在输出带的第一个方格上输出一个整且在输出带的第一个方格上输出一个整数数y y后停机，那么就说程序后停机，那么就说程序P P计
8、算了函数计算了函数 f(xf(x1 1，x x2 2，x xn n)=y)=y 计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性解释二：解释二：把把RAMRAM程序当作一个语言接受器程序当作一个语言接受器将字符串将字符串S=aS=a1 1a a2 2a an n放在输入带上。放在输入带上。在输入带的第一个方格中放入符号在输入带的第一个方格中放入符号a a1 1，第第二个方格中放入符号二个方格中放入符号a a2 2，第第n n个方格个方格中放入符号中放入符号a an n。然后在第然后在第n+1n+1个方格中放个方格中放入入0 0，作为输入串的结束标志符。，作为输入串的结束标志符
9、。如果一个如果一个RAMRAM程序程序P P读了字符串读了字符串S S及结及结束标志符束标志符0 0后，在输出带的第一格输出一后，在输出带的第一格输出一个个1 1并停机，就说程序并停机，就说程序P P接受字符串接受字符串S S。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性3.3.RAMRAM程序的耗费标准程序的耗费标准标准一：标准一：均匀耗费标准均匀耗费标准在均匀耗费标准下，每条在均匀耗费标准下，每条RAMRAM指指令需要一个单位时间；每个寄存器令需要一个单位时间；每个寄存器占用一个单位空间。占用一个单位空间。RAM RAM程序的复杂性一般按照均匀程序的复杂性一般按照均匀
10、耗费标准衡量。耗费标准衡量。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性标准二：标准二：对数耗费标准对数耗费标准对数耗费标准是基于这样的假对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比进制表示的指令的操作数长度成比例。在例。在RAMRAM计算模型下，假定一个寄计算模型下，假定一个寄存器可存放一个任意大小的整数。存器可存放一个任意大小的整数。因此若设因此若设l(i)l(i)是整数是整数i i所占的二进制所占的二进制位数，则位数，则 001|log)(iiiil计算复杂性计算复杂性问题问题 第第8 8课课
11、计算复杂性计算复杂性随机存取机随机存取机RASPRASP1.1.RASPRASP的结构的结构RASPRASP的整体结构类似于的整体结构类似于RAMRAM，所所不同的是不同的是RASPRASP的程序是存储在寄存的程序是存储在寄存器中的。每条器中的。每条RASPRASP指令占据指令占据2 2个连续个连续的寄存器。第一个寄存器存放操作的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址码的编码，第二个寄存器存放地址。RASPRASP指令用整数进行编码。指令用整数进行编码。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性2.2.RASPRASP程序的复杂性程序的复杂性不管是在
12、均匀耗费标准下，还不管是在均匀耗费标准下，还是在对数耗费标准下，是在对数耗费标准下，RAMRAM程序和程序和RASPRASP程序的复杂性只差一个常数因程序的复杂性只差一个常数因子。在一个计算模型下子。在一个计算模型下T(n)T(n)时间内时间内完成的输入完成的输入-输出映射可在另一个计输出映射可在另一个计算模型下模拟，并在算模型下模拟，并在kT(n)kT(n)时间内完时间内完成。其中成。其中k k是一个常数因子。空间复是一个常数因子。空间复杂性的情况也是类似的。杂性的情况也是类似的。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机图灵机1 1、图灵机的构成、图灵机的构
13、成 图灵机由一个控制器和一条无限长图灵机由一个控制器和一条无限长的工作带组成，的工作带组成，工作带：划分为许多单元，每个单工作带：划分为许多单元，每个单元可以存放字母表元可以存放字母表 中的一个符号。中的一个符号。控制器：具有有穷个内部状态和一控制器：具有有穷个内部状态和一个读写头。个读写头。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性单带图灵机结构单带图灵机结构 计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性图灵机的工作过程图灵机的工作过程 计算的每一步，控制器处于某个状计算的每一步，控制器处于某个状态，读写头扫描工作带的某一个单元符态，读写头扫描工
14、作带的某一个单元符号；根据当前状态、被扫描单元的内容号；根据当前状态、被扫描单元的内容，决定下一步的执行动作：，决定下一步的执行动作：把当前单元内容，改写成某一个符把当前单元内容，改写成某一个符号；使读写头停止不动、向左或向右移号；使读写头停止不动、向左或向右移动一个单元；使控制器转移到某一个状动一个单元；使控制器转移到某一个状态等等。态等等。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 计算开始时，输入符号串放在计算开始时，输入符号串放在工作带上，控制器处于初始状态工作带上，控制器处于初始状态 ，读写头扫描输入符号串左端的第一读写头扫描输入符号串左端的第一个符号；个符号
15、；如果对于当前的状态和所扫描如果对于当前的状态和所扫描的符号，没有下一步的动作，则图的符号，没有下一步的动作，则图灵机就停止计算。灵机就停止计算。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机形式定义图灵机形式定义 图灵机图灵机 是一个六元组：是一个六元组：S S：控制器的非空有限状态集合；：控制器的非空有限状态集合；：有限工作带符号集合，含空白符：有限工作带符号集合，含空白符B B；：输入符号字母表，：输入符号字母表，；P P0 0：初始状态，：初始状态，；P Pf f：最终状态或接受状态，：最终状态或接受状态，；：转移函数。：转移函数。),(0fppSMBSp
16、0Spf计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性转移函数转移函数的说明的说明转移函数的定义域：转移函数的定义域：转移函数的值域：转移函数的值域：Sdom)(,)()(RPLBSran计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 L,P,R L,P,R 读写头的动作读写头的动作:L:L:左移一个单元；左移一个单元；P:P:停止不动；停止不动；R:R:右移一个单元；右移一个单元；转移函数的含义：转移函数的含义：控制器当前状态为控制器当前状态为P P 、读写头扫描、读写头扫描到的符号为到的符号为x x 时，把控制器状态修改为时，把控制器状态修改为P P
17、；把符号修改为符号；把符号修改为符号xx ；使读写头；使读写头向右移动一个单元。向右移动一个单元。),(),(Rxpxp计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机格局定义图灵机格局定义 是一个图灵机，是一个图灵机，M M 的的格局是一个二元组：格局是一个二元组：:是工作带上的内容。是工作带上的内容。:表示在此格局下读写头的位置；表示在此格局下读写头的位置；1 1 :表示处于读写头左边的符号串；表示处于读写头左边的符号串；2 2 :表示处于读写头右边的符号串。表示处于读写头右边的符号串。读写头指向符号串读写头指向符号串2 2 的第一个符号。的第一个符号。),(0f
18、ppSM),(21 p21,计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性图灵机格局图灵机格局初始格局：初始格局：，1 1 为空串；为空串；可接受格局：可接受格局：，P P 是可接是可接受状态，即受状态，即 。停机格局：停机格局：中，中，2 2 的第一的第一个符号是个符号是x x ，转移函数，转移函数 没有定没有定义，则称义，则称是停机格局。是停机格局。),(00 p),(21 pfpp),(21 p),(xp计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机的计算图灵机的计算 是一个有穷、或无穷的是一个有穷、或无穷的格局序列，如果每一个格局序列，如
19、果每一个i+1i+1 都由都由i i 经经过一步得到，称这个序列是一个计算。过一步得到，称这个序列是一个计算。,21n计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机计算的停机状态图灵机计算的停机状态1 1）计算是有穷序列）计算是有穷序列 ，是可，是可接受的停机格局，称停机在接受状态。接受的停机格局，称停机在接受状态。称图灵机称图灵机 M M 接受符号串接受符号串 ；2 2）计算是有穷序列）计算是有穷序列 ，不是可不是可接受的停机格局，称停机在拒绝状态。接受的停机格局，称停机在拒绝状态。称图灵机称图灵机 M M 不接受符号串不接受符号串 ，或拒绝，或拒绝符号串符号串;
20、3 3）计算是无穷序列）计算是无穷序列 ，永不，永不停机。停机。n,10n,10,21n计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机对语言的识别图灵机对语言的识别构造一个识别语言构造一个识别语言 的图灵机的图灵机设计思想：设计思想：使读写头来回移动，成对地对输入使读写头来回移动，成对地对输入符号串的左端和右端作标记。符号串的左端和右端作标记。如果全部符号都作了标记，则左边如果全部符号都作了标记，则左边的与右边的个数相等，的与右边的个数相等，；否则，；否则，。1|nbaLnnLL计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机的构造图灵机的
21、构造S=S=P P0 0,P,P1 1,P,P2 2,P,P3 3,P,P4 4,P,PN N ;=a,b,x,Ba,b,x,B;=a,b,a,b,;P Pf f=P P4 4,P,PN N ;其中，其中，P P4 4 为接受状态，为接受状态，P PN N 为拒绝状为拒绝状态。态。,),(0fppSM计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性转移函数转移函数(p p0 0,a a)=)=(p p0 0,b b)=)=(p p1 1,a a)=)=(p p1 1,x x)=)=(p p1 1,B)=,B)=(p p2 2,b b)=)=(p p2 2,x x)=)=(p
22、p2 2,B)=,B)=(p p3 3,a a)=)=(p p3 3,x x)=)=(p p3 3,B,B )=)=),(p),(0Rap),(1Lxp),(2Rxp),(1Lxp),(RBpN),(1Lxp),(2Rxp),(3LBp),(RapN),(3Lxp),(4RBp计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 对于对于 ，设，设n=2n=2，图灵机的，图灵机的工作过程如下：工作过程如下：1|nbaLnn),(00aabbBBp),(0Rap),(01abbBBap),(0Rap),(02bbBBaap),(1Lxp),(13xbBBaap),(2Rxp),(2
23、4xbBBaxp),(2Rxp),(25bBBaxxp),(1Lxp计算复杂性计算复杂性 第第8 8课课 计算复杂性计算复杂性 ),(16xBBaxxp),(1Lxp),(17xxBBaxp),(1Lxp),(18xxxBBap),(2Rxp),(29xxxBBxp),(2Rxp),(210 xxBBxxp),(2Rxp),(211xBBxxxp),(2Rxp),(212BBxxxxp),(3LBp计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 ),(313BBxxxxp),(3Lxp),(314xBBxxxp),(3Lxp),(315xxBBxxp),(3Lxp),(31
24、6xxxBBxp),(3Lxp),(317xxxxBBp),(4RBp),(418xxxxBBp计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 K K带图灵机结构带图灵机结构 有有K K个工作带，每个工作带有一个读个工作带，每个工作带有一个读写头，都可以独立地移动。写头，都可以独立地移动。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 K K带图灵机形式定义带图灵机形式定义转移函数转移函数的形式：的形式：K K带图灵机格局带图灵机格局若若x x是输入符号串，则初始格局表示为是输入符号串，则初始格局表示为 ),(0fppSM),(,),(,),(,(),(
25、221121kkkDxDxDxpxxxp),(2122211211kkp),(0BBxp计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 确定的图灵机和非确定的图灵机确定的图灵机和非确定的图灵机确定性图灵机确定性图灵机 若图灵机的转移函数若图灵机的转移函数是单值的，是单值的，则称该图灵机为确定性图灵机，记为则称该图灵机为确定性图灵机，记为 DTMDTM，图灵机每一步的动作都是确定的。，图灵机每一步的动作都是确定的。非确定的图灵机非确定的图灵机 若图灵机的转移函数若图灵机的转移函数是多值的，是多值的，则称该图灵机为非确定性图灵机，记为则称该图灵机为非确定性图灵机，记为 NDTM
26、NDTM。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机的执行时间图灵机的执行时间图灵机的计算的长度图灵机的计算的长度 设设 是一个格局序列，它是一个格局序列，它是图灵机对输入的一个计算。如果是图灵机对输入的一个计算。如果t t 是是一个可接受的停机格局，则称这个计算一个可接受的停机格局，则称这个计算是可接受的计算，是可接受的计算，t t 称为这个计算的长称为这个计算的长度。度。t,21计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性图灵机的执行时间图灵机的执行时间 图灵机图灵机M M 对输入对输入x x进行计算的执行进行计算的执行时间，记为时间，
27、记为T TM M(x)(x)，它定义为：，它定义为：(1)(1)如果如果M M 对输入对输入x x有一个可接受的计算有一个可接受的计算，则，则T TM M(x)(x)是最短的可接受计算的长度；是最短的可接受计算的长度；(2)(2)如果如果M M 对输入对输入 x x没有一个可接受的没有一个可接受的计算，则计算，则 T TM M(x)=(x)=。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机的时间复杂性图灵机的时间复杂性 图灵机图灵机M M的时间复杂性的时间复杂性T(n)T(n)是它处理是它处理所有长度为所有长度为n n的输入所需的最大计算步数的输入所需的最大计算步数
28、。如果对某个长度为。如果对某个长度为n n的输入，图灵机不的输入，图灵机不停机，停机，T(n)T(n)对这个对这个n n值无定义。值无定义。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 图灵机的空间复杂性图灵机的空间复杂性 图灵机的空间复杂性图灵机的空间复杂性S(n)S(n)是它处理是它处理所有长度为所有长度为n n的输入时，在的输入时，在k k条带上所使条带上所使用过的方格数的总和。如果某个读写头用过的方格数的总和。如果某个读写头无限地向右移动而不停机，无限地向右移动而不停机，S(n)S(n)也无定也无定义。义。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计
29、算复杂性 图灵机模型与图灵机模型与RAMRAM模型的关系模型的关系 图灵机模型与图灵机模型与RAMRAM模型的关系是指同模型的关系是指同一问题在这两种不同计算模型下的复杂一问题在这两种不同计算模型下的复杂性之间的关系。性之间的关系。对于问题对于问题P P的任何长度为的任何长度为n n的输入，的输入，设求解问题设求解问题P P的算法的算法A A在在k k带图灵机模型带图灵机模型TMTM下的时间复杂性为下的时间复杂性为T(n)T(n)，那么，算法，那么，算法A A在在RAMRAM模型下的时间复杂性为模型下的时间复杂性为O(TO(T2 2(n)(n)。计算复杂性计算复杂性问题问题 第第8 8课课 计
30、算复杂性计算复杂性 对于问题对于问题P P的任何长度为的任何长度为n n的输入，设的输入，设求解问题求解问题P P的算法的算法A A在在RAMRAM模型下，不含有乘模型下，不含有乘法和除法指令，且按对数耗费标准其时间复法和除法指令，且按对数耗费标准其时间复杂性为杂性为T(n)T(n)，那么，算法，那么，算法A A在在k k带图灵机模型带图灵机模型TMTM下的时间复杂性为下的时间复杂性为O(TO(T2 2(n)(n)。通过问题变换的技巧，可以将不同问题通过问题变换的技巧，可以将不同问题的计算复杂性联系在一起。这样就可以将一的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的
31、计个问题的计算复杂性归结为另一个问题的计算复杂性。算复杂性。计算复杂性计算复杂性问题问题 第第8 8课课 计算复杂性计算复杂性 易解的问题和难解的问题易解的问题和难解的问题存在多项式时间算法的问题，称为存在多项式时间算法的问题，称为易解的问题。易解的问题。指数时间算法或排列时间算法的问指数时间算法或排列时间算法的问题，称为难解的问题。题，称为难解的问题。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 难解问题的计算相关性难解问题的计算相关性计算相关：计算相关：某类问题可以归约为另一类问题。某类问题可以归约为另一类问题。计算相关问题计算相关问题 若它们之一可用多项式时间
32、求解，若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找法，则同类的其它问题，也肯定不会找到多项式时间算法。到多项式时间算法。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 P P类和类和NPNP类语言的定义类语言的定义 P=L|LP=L|L是一个能在多项式时间是一个能在多项式时间内被一台内被一台DTMDTM所接受的语言所接受的语言 NP=L|L NP=L|L是一个能在多项式时间是一个能在多项式时间内被一台内被一台NDT
33、MNDTM所接受的语言所接受的语言 P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性判定问题和优化问题判定问题和优化问题判定问题判定问题:只牵涉到两种情况：只牵涉到两种情况：YES YES 或或 NONO，可以容易地表达为语言的识别问题，可以容易地表达为语言的识别问题，方便在图灵机上进行求解。，方便在图灵机上进行求解。例如：排序问题的判定问题。给定一个例如：排序问题的判定问题。给定一个整数数组，是否可以按非降顺序排序；整数数组，是否可以按非降顺序排序；图着色的判定问题。给定无向图图着色的判定问题。给定无向图 ，是否，是否可用可用K K种颜色为种颜色为N N中的每一个顶点
34、分配一中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有种颜色，使得不会有两个相邻顶点具有同一种颜色。同一种颜色。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 优化问题优化问题优化问题牵涉到极值问题。优化问题牵涉到极值问题。例：图着色的优化问题。例：图着色的优化问题。为图为图G G着色，使相邻两个顶点不会有着色，使相邻两个顶点不会有相同颜色时所需要的最少颜色数目。相同颜色时所需要的最少颜色数目。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性例：求解为图例：求解为图G G着色，使相邻两个顶点不着色，使相邻两个顶点不会有相同颜色时所需最少颜
35、色数会有相同颜色时所需最少颜色数numnum。令图令图G G的顶点个数为的顶点个数为n n，彩色数是，彩色数是numnum，假定存在一个图假定存在一个图G G着色判定问题的多项式着色判定问题的多项式时间算法时间算法coloringcoloring：BOOL coloring(GRAPH G,int n,int num)BOOL coloring(GRAPH G,int n,int num)则可用下面的方法，利用算法则可用下面的方法，利用算法coloringcoloring来解图着色的优化问题。来解图着色的优化问题。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性void
36、 chromatic_number(GRAPH G,int void chromatic_number(GRAPH G,int n,int&num)n,int&num)int high,low;int high,low;high=n;high=n;low=1;low=1;while(low=high)while(low=high)P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 num=(low+high)/2;num=(low+high)/2;if(coloring(G,n,num)if(coloring(G,n,num)low=mid+1;low=mid+1;els
37、e else high=mid 1;high=mid 1;num=high;num=high;P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性判定问题转换为优化问题判定问题转换为优化问题 对算法对算法coloringcoloring调用调用O O(log n)(log n)次，就能找出为图着色的最优彩色次，就能找出为图着色的最优彩色数。数。根据假定，根据假定，coloringcoloring是多项式是多项式时间算法时间算法;所以，这个算法也是一个多项所以，这个算法也是一个多项式时间算法。式时间算法。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性
38、 P P类问题类问题确定性算法确定性算法 若若A A是问题是问题的一个算法。如果在处的一个算法。如果在处理问题理问题的实例时，在算法的整个执行的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，过程中，每一步只有一个确定的选择，就说算法就说算法A A是确定性的算法。是确定性的算法。含义：算法执行的每一个步骤，都含义：算法执行的每一个步骤，都有确定的选择。重新用同一输入实例运有确定的选择。重新用同一输入实例运行该算法，所得到的结果严格一致。行该算法，所得到的结果严格一致。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 P P类判定问题类判定问题 如果对某个判定问
39、题如果对某个判定问题，存在着一，存在着一个非负整数个非负整数K K，对输入规模为，对输入规模为n n的实例，的实例，能够以能够以O O(n(nk k)的时间运行一个确定性的算的时间运行一个确定性的算法，得到法，得到 YES YES 或或NO NO 的答案，则该判定的答案，则该判定问题问题是一个是一个P P类判定问题。类判定问题。特性：特性：P P类判定问题是由具有多项式类判定问题是由具有多项式时间的确定性算法来解的判定问题。时间的确定性算法来解的判定问题。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性例如：例如：最短路径判定问题最短路径判定问题 给定有向赋权图给定有向
40、赋权图G G（权为正整数）、（权为正整数）、正整数正整数K K、及两个顶点、及两个顶点s,t s,t，是否存在着，是否存在着一条由一条由s s到到t t、长度至多为、长度至多为K K的路径。的路径。可排序的判定问题可排序的判定问题 给定给定n n个元素的数组，是否可以按非个元素的数组，是否可以按非降顺序排序。降顺序排序。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 P P类判定问题的补类判定问题的补 改变判定问题的提法，改变判定问题的提法，“是否不可是否不可以以”、“是否不存在是否不存在”的判定问题。的判定问题。例：例：可排序判定问题的补可排序判定问题的补 给定给定
41、n n个元素的数组，是否不可以按个元素的数组，是否不可以按非降顺序排序。非降顺序排序。最短路径判定问题的补最短路径判定问题的补 给定有向赋权图给定有向赋权图G G（权为正整数）、（权为正整数）、正整数正整数K K、及两个顶点、及两个顶点s s、t t，是否不存，是否不存在着一条由在着一条由s s到到t t、长度至多为、长度至多为K K的路径。的路径。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 P P类问题的封闭性类问题的封闭性 令令C C是一类问题，如果对是一类问题，如果对C C中的任何中的任何问题问题C C，的补也在的补也在C C中，则称中，则称C C类类问题在
42、补集下封闭。问题在补集下封闭。P P类问题的封闭性类问题的封闭性:P P类问题在补集下是封闭的。类问题在补集下是封闭的。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性归约的定义归约的定义 令令和和是两个判定问题，如果是两个判定问题，如果存在一个确定性算法存在一个确定性算法A A，可以用多项式，可以用多项式的时间，把问题的时间，把问题的实例的实例II转换为问转换为问题题的实例的实例I I，使得的答案为，使得的答案为yes yes，当且，当且仅当仅当I I的答案是的答案是yes yes。就说，。就说，以多项以多项式时间归约于式时间归约于，记为，记为p p 。P P类与类与
43、NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 P P类问题的归约性类问题的归约性 和和是两个判定问题，是两个判定问题，如果如果,P P，并且，并且，p p ，则，则P P。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 NP NP类问题类问题非确定性算法非确定性算法 问题问题的非确定性算法的分为两个的非确定性算法的分为两个阶段：推测阶段和验证阶段。阶段：推测阶段和验证阶段。推测阶段推测阶段 对规模为对规模为n n的输入实例的输入实例x x，以多项式，以多项式时间时间O O(n(ni i)产生输出产生输出y y，而不管，而不管y y的正确性的正确性。P P
44、类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性验证阶段验证阶段 以多项式时间以多项式时间O O(n(nj j)的确定性算法的确定性算法验证两件事情：验证两件事情：1 1）检查上一阶段的输出）检查上一阶段的输出y y是否具有正是否具有正确的形式。如果确的形式。如果y y不具正确的形式，算法不具正确的形式，算法就以答案就以答案nono结束；结束；2 2）如果）如果y y具有正确的形式，则继续检具有正确的形式，则继续检查查 是否是问题的输入实例是否是问题的输入实例x x 的解。如果的解。如果它确实是问题实例它确实是问题实例x x的解，则以答案的解，则以答案yesyes结束，否则，
45、以答案结束，否则，以答案nono结束。结束。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 旅行售货商的判定问题旅行售货商的判定问题 给定给定n n个城市、正常数个城市、正常数k k、及城市之、及城市之间的费用矩阵间的费用矩阵C C ，判定是否存在一条经，判定是否存在一条经过所有城市一次且仅一次、最后返回初过所有城市一次且仅一次、最后返回初始出发城市、且费用小于常数始出发城市、且费用小于常数k k的回路。的回路。令令A A是求旅行售货商判定问题的算法。是求旅行售货商判定问题的算法。A A用非确定性的方法，在多项式时间用非确定性的方法，在多项式时间内推测存在着一条回路，
46、假定它是问题内推测存在着一条回路，假定它是问题的解的解;P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 A A用确定性的算法，在多项式时间内用确定性的算法，在多项式时间内检查：该回路是否是哈密尔屯回路，检查：该回路是否是哈密尔屯回路，如果答案为如果答案为yes yes，则继续检查该回路的，则继续检查该回路的费用是否小于常数费用是否小于常数C C，如果答案仍为，如果答案仍为yes yes，则算法，则算法A A输出输出yes yes，否则输出，否则输出no no。因此，因此，A A是求解旅行售货商判定问题是求解旅行售货商判定问题的非确定性算法。的非确定性算法。P P类与类
47、与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 非确定性算法的运行时间非确定性算法的运行时间 非确定性算法的运行时间，是推测非确定性算法的运行时间，是推测阶段和验证阶段运行时间的和。阶段和验证阶段运行时间的和。若推测阶段的运行时间为若推测阶段的运行时间为O O(n(ni i)，验证阶段的运行时间为验证阶段的运行时间为O O(n(nj j)，则对某个非负整数则对某个非负整数k k，非确定性算法，非确定性算法的运行时间为的运行时间为O O(n(ni i)+)+O O(n(nj j)=)=O O(n(nk k)。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性
48、NP NP类判定问题类判定问题 如果对某个判定问题如果对某个判定问题，存在着一，存在着一个非负整数个非负整数k k，对输入规模为，对输入规模为n n的实例，的实例，能够以能够以O O(n(nk k)的时间运行一个非确定性的的时间运行一个非确定性的算法，得到算法，得到yesyes或或nono的答案，则该判定问的答案，则该判定问题题是一个是一个NPNP类判定问题。类判定问题。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 旅行售货商问题旅行售货商问题 若算法若算法A A可在推测阶段用多项式时间可在推测阶段用多项式时间推测出一条回路，并假定它是问题的解推测出一条回路，并假定
49、它是问题的解；在验证阶段用多项式时间的确定性算；在验证阶段用多项式时间的确定性算法，检查所推测的回路是否恰好每个城法，检查所推测的回路是否恰好每个城市经过一次，如果是，再进一步判断这市经过一次，如果是，再进一步判断这条回路的长度是否小于或等于条回路的长度是否小于或等于L L，如果是，如果是，答案为，答案为yesyes，否则，答案为，否则，答案为nono。根据定义，旅行售货商判定问题是根据定义，旅行售货商判定问题是NPNP类判定问题。类判定问题。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 P P类问题和类问题和NPNP类问题的差别类问题的差别 P P类问题可以用多项
50、式时间的确定性类问题可以用多项式时间的确定性算法来进行判定或求解；算法来进行判定或求解；NPNP类问题可以用多项式时间的确定类问题可以用多项式时间的确定性算法来检查和验证它的解。性算法来检查和验证它的解。P P，必然有，必然有NP NP，所以，所以，P P NP NP。猜测猜测 PNPPNP。该不等式是否成立、。该不等式是否成立、至今还没有得到证明。至今还没有得到证明。P P类与类与NPNP类问题类问题 第第8 8课课 计算复杂性计算复杂性 NP NP完全问题概念完全问题概念NPNP难题难题 令令是一个判定问题，如果对是一个判定问题，如果对NP NP 中中的每一个问题的每一个问题NP NP ，
