《第九章NP完全性理论与近似计算》由会员分享，可在线阅读，更多相关《第九章NP完全性理论与近似计算（60页珍藏版）》请在金锄头文库上搜索。
1、第第9 9章章 NPNP完全性理论与近似计算完全性理论与近似计算上海大学计算机学院上海大学计算机学院 9.1 计算模型计算模型9.1.1 随机存取机随机存取机RAM9.1.2 随随机机存存取取存存储储程程序序机机RASP9.1.3 图灵机图灵机9.2 P类与类与NP类问题类问题9.2.1 非确定性图灵机非确定性图灵机9.2.2 P类与类与NP类语言类语言9.2.3 多项式时间验证多项式时间验证9.3 NP完全问题完全问题9.3.1 多项式时间变换多项式时间变换本章主要知识点本章主要知识点9.3.2一些典型的一些典型的NP完全问题完全问题9.4 NP完全问题的近似算法完全问题的近似算法9.4.1
2、 近似算法的性能近似算法的性能9.4.2 顶顶点点覆覆盖盖问问题题的的近近似似算算法法9.4.3 旅旅行行售售货货员员问问题题近近似似算算法法9.4.4 集集合合覆覆盖盖问问题题的的近近似似算算法法9.4.5 子集和问题的近似算法子集和问题的近似算法引 言1 1、何为何为“好的好的”算法？算法？1.1.Cobham1964Cobham1964和和Edmonds1965Edmonds1965首先加以区别。首先加以区别。EdmondsEdmonds把多项式时间算法与把多项式时间算法与“好的好的”算法等同算法等同看待，并猜想某些整数规划问题可能不能用这种看待，并猜想某些整数规划问题可能不能用这种“好
3、的好的”算法求解。算法求解。2.2.一般观点：认为指数时间算法不应该算作一般观点：认为指数时间算法不应该算作“好的好的”算法。算法。大多数指数时间算法只是穷举搜索法的变种大多数指数时间算法只是穷举搜索法的变种多项式时间算法通常只有在对问题的结构有了某些比多项式时间算法通常只有在对问题的结构有了某些比较深入地了解之后才有可能给出较深入地了解之后才有可能给出3.3.计算机科学家们：多顶式时间算法和指数时间算计算机科学家们：多顶式时间算法和指数时间算法之间的区别明显。法之间的区别明显。2 2、什么问题、什么问题“易计算易计算”？“难计算难计算”？只有用多项式时间算法解决的问题才能认为只有用多项式时间
4、算法解决的问题才能认为“易计算易计算”的。的。一般，如果一个问题困难到不可能用多项式一般，如果一个问题困难到不可能用多项式时间算法求解，则认为这个问题是时间算法求解，则认为这个问题是“难解的难解的”。上述按能否用上述按能否用“多项式时间算法解决问题多项式时间算法解决问题”来理解一个问题是否来理解一个问题是否“易计算易计算”或或“难解的难解的”是不深刻的。是不深刻的。3、有关时间复杂性问题的探讨、有关时间复杂性问题的探讨时间复杂性是一种最坏情况的度量时间复杂性是一种最坏情况的度量。时间复杂性为2n的算法仅仅表示至少有一个规模为n的问题实例需要这么多的运算时间，而大多数问题实例可能需要远比2n少得
5、多的时间。例如：几个著名的算法a)线性规划的单纯形算法：单纯形算法：已经证明具有指数时间复杂性Klee & Minty，1972，但是在实际中它计算得很好。b)b)背包问题背包问题的分支限界算法：分支限界算法：虽然也具有指数时间复杂性，但是它是一种非常成功的算法，使得许多人认为背包问题已经很好地解决了。注：具有指数时间但计算得很好的例子很少。注：具有指数时间但计算得很好的例子很少。探讨（续）探讨（续）一些问题尽管有一些问题尽管有指数计算时间指数计算时间，但算法，但算法很成功。研究人员没有停止继续寻找该很成功。研究人员没有停止继续寻找该类问题的类问题的多项式时间算法多项式时间算法的努力。的努力。
6、疑问：出现上述现象的问题其关键性的疑问：出现上述现象的问题其关键性的性质是什么？性质是什么？v对这些性质的仔细研究可能给出更好的方对这些性质的仔细研究可能给出更好的方法，但至今在解释这种成功方面几乎毫无法，但至今在解释这种成功方面几乎毫无进展，也没有一种方法能够事先预言给定进展，也没有一种方法能够事先预言给定的指数时间算法在实际中能否快速运算。的指数时间算法在实际中能否快速运算。4 4、“可证地有效可证地有效”算法具有时间复杂性为n100或1099n2的算法，能称快速运算吗？实际情况是，多项式可解的问题大多数可用2次，或者在最坏的情况下用3次多项式时间算法求解，而且在多项式中不包含特别大的系数
7、。满足这些限制的算法可认为是“可证地有可证地有效效”算法。5、一些初步概念1. 问题可解：指有一定算法，在有限步内解决问题问题可解：指有一定算法，在有限步内解决问题 3. 可有效解决的问题：有一个算法可在多项式时间可有效解决的问题：有一个算法可在多项式时间中完成其计算的问题中完成其计算的问题 4. P类问题：类问题：在多项式时间算法内求解的问题在多项式时间算法内求解的问题2. 有效算法：运行时间是关于输入规模有效算法：运行时间是关于输入规模n的函数的函数f(n)至多是多项式界的算法至多是多项式界的算法 5. NP问题问题“难解的难解的”问题，用不确定性计算机问题，用不确定性计算机（模型）求解时
8、间复杂性为多项式，记（模型）求解时间复杂性为多项式，记NP9.1 计算模型计算模型计算模型计算模型概述概述计算机模型：计算机模型：是作复杂性分析的依据和客观尺度是作复杂性分析的依据和客观尺度1.三种最基本的计算模型：三种最基本的计算模型：1、随机存取存储程序机、随机存取存储程序机 RASP 2、图灵机图灵机TM（单带图灵机，多带图灵机）单带图灵机，多带图灵机）3、随机存取机（、随机存取机（RAM）2.研究结果：研究结果：至今研究过的所有实际的计算机模型，例如单至今研究过的所有实际的计算机模型，例如单带图灵机、多带图灵机以及随机存取机（带图灵机、多带图灵机以及随机存取机（RAM），），都是都是相
9、相对于对于多项式时间复杂性等价的，但在计算速度上不同。多项式时间复杂性等价的，但在计算速度上不同。3. “合理的合理的”计算机模型：计算机模型：也称为是也称为是“确定性确定性”的的计算机模计算机模型。不能认为具有完成任意多道并行运算能力的模型是型。不能认为具有完成任意多道并行运算能力的模型是“合理的合理的”，因他们是，因他们是“不确定的不确定的” 。9.1.1 随机存取机随机存取机RAMRAM1、RAMRAM的结构的结构2、RAMRAM程序程序一个一个RAM程序定义了从输入带到输出带的一个映射。程序定义了从输入带到输出带的一个映射。可以对这种映射关系作可以对这种映射关系作2 2种不同的解释：种
10、不同的解释：解释一：把解释一：把RAMRAM程序看成是计算一个函数程序看成是计算一个函数若一个若一个RAMRAM程序程序P P总是从输入带前总是从输入带前n n个方格中读入个方格中读入n n个整数个整数x x1 1，x x2 2，x xn n，并且在输出带的第一个方格上输出一个整数并且在输出带的第一个方格上输出一个整数y y后停机，那么就说程序后停机，那么就说程序P P计算了函数计算了函数f(xf(x1 1，x x2 2，x xn n)=y )=y 解释二：把解释二：把RAMRAM程序当作一个语言接受器。程序当作一个语言接受器。将字符串将字符串S=aS=a1 1a a2 2aan n放在输入带
11、上。在输入带的第一个，放在输入带上。在输入带的第一个，第二个，第二个，第，第n n个方格中依次放入符号个方格中依次放入符号a a1 1，a a2 2，a an n。然后然后在第在第n+1n+1个方格中放入个方格中放入0 0，作为输入串的结束标志符。如果一个，作为输入串的结束标志符。如果一个RAMRAM程序程序P P读了字符串读了字符串S S及结束标志符及结束标志符0 0后，在输出带的第一格输后，在输出带的第一格输出一个出一个1 1并停机，就说程序并停机，就说程序P P接受字符串接受字符串S S。 3、 RAMRAM程序的耗费标准程序的耗费标准标准一：均匀耗费标准标准一：均匀耗费标准 在均匀耗费
12、标准下，每条在均匀耗费标准下，每条RAMRAM指令需要一个单位时间；每个指令需要一个单位时间；每个寄存器占用一个单位空间。寄存器占用一个单位空间。RAMRAM程序的复杂性一般按照均匀程序的复杂性一般按照均匀耗费标准来衡量。耗费标准来衡量。标准二：对数耗费标准标准二：对数耗费标准 对数耗费标准假定，执行一条指令的耗费与以二进制表示的对数耗费标准假定，执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在指令的操作数长度成比例。在RAMRAM计算模型下，假定一个寄计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设存器可存放一个任意大小的整数。因此若设l(i)l(i)是整数是整数i
13、i所所占的二进制位数，则占的二进制位数，则 9.1.2 随机存取存储程序机随机存取存储程序机RASPRASP1、RASPRASP的结构的结构vRASP的整体结构类似于的整体结构类似于RAM，所不同的是所不同的是RASP的程序是存储在寄存器中的。每条的程序是存储在寄存器中的。每条RASP指令占据指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。第二个寄存器存放地址。RASP指令用整数指令用整数（118）进行编码。）进行编码。 2、RASPRASP程序程序的复杂性的复杂性不管是在均匀耗费标准下，还是在对数耗费标准不管是在均匀
14、耗费标准下，还是在对数耗费标准下，下，RAMRAM程序和程序和RASPRASP程序的复杂性只差一个常数程序的复杂性只差一个常数因子。在一个计算模型下因子。在一个计算模型下T(n)T(n)时间内完成的输入时间内完成的输入- -输出映射可在另一个计算模型下模拟，并在输出映射可在另一个计算模型下模拟，并在kT(nkT(n) )时间内完成。其中时间内完成。其中k k是一个常数因子。空间是一个常数因子。空间复杂性的情况也是类似的。复杂性的情况也是类似的。 9.1.3 图灵机图灵机 0、有穷自动机（补充）、有穷自动机（补充）确定型有穷自动机的定义：确定型有穷自动机的定义： 一台确定型有穷自动机是一个五元组
15、一台确定型有穷自动机是一个五元组（Q, , , S, F)。其中，其中， Q, , 都是有穷集合。都是有穷集合。Q：有穷状态集合有穷状态集合 ：字母表：字母表S: 初始状态，初始状态， S QF: 终止状态集合，终止状态集合，F Q : 转移函数，转移函数， : Q Q确定性有穷自动机举例确定性有穷自动机举例例：一台确定型有穷自动机，它接受这样的语言：由例：一台确定型有穷自动机，它接受这样的语言：由a,b字符构成、不含字符构成、不含3个连续个连续b字符的有限长度的字符串。字符的有限长度的字符串。Q = q0, q1, q2, q3 = a, b S = q0F = q0, q1, q2 采用状
16、态图表示：采用状态图表示：q0q1 q2 q3aaaabbbb有穷自动机的一种表示有穷自动机的一种表示 有有 穷穷 q0 q1 q2 q3 控制器控制器 a b a b a a b a b b a a读头读头输入带输入带1. 多带图灵机多带图灵机结构：结构：有限状态控制器、有限状态控制器、k条读条读/写头写头（双向移动）（双向移动）、k条读写带条读写带 2. 2. 单带图灵机单带图灵机 有有 穷穷 q0 q1 q2 q3 控制器控制器 读读/写头写头带带（双向（双向移动）移动） b a b a b b 3 3、图灵机结构特点、图灵机结构特点（1）读读/写头写头既能读，又能写。既能读，又能写。（
17、2）读写头能左）读写头能左/右移动，但不会移出带右移动，但不会移出带的左端。的左端。（3）“带带”无限长，上置所读无限长，上置所读/写的字符写的字符和特殊符号。和特殊符号。（4）有穷控制器内置各种状态。）有穷控制器内置各种状态。4 4、有限状态控制器的作用、有限状态控制器的作用根据有限状态控制器的当前状态及每个读写头读到的带根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面符号，图灵机的一个计算步可实现下面3 3个操作之一或全个操作之一或全部。部。 (1)(1)改变有限状态控制器中的状态。改变有限状态控制器中的状态。 (2)(2)清除当前读写头下的方格中原有带符
18、号并写上新的带清除当前读写头下的方格中原有带符号并写上新的带符号。符号。 (3)(3)独立地将任何一个或所有读写头，向左移动一个方格独立地将任何一个或所有读写头，向左移动一个方格(L)(L)或向右移动一个方格或向右移动一个方格(R)(R)或停在当前单元不动或停在当前单元不动(S)(S)。 5 5、k k带图灵机可形式化地描述带图灵机可形式化地描述k k带图灵机可形式化地描述为一个带图灵机可形式化地描述为一个7 7元组元组 (Q(Q，T T，I I，B B，q q0 0，q qf f) )，其中其中: : (1)Q (1)Q是有限个状态的集合。是有限个状态的集合。 (2)T(2)T是有限个带符号
19、的集合。是有限个带符号的集合。 (3)I(3)I是输入符号的集合，是输入符号的集合，I I T T。 (4)B(4)B是唯一的空白符，是唯一的空白符，BT-IBT-I。 (5)q(5)q0 0是初始状态。是初始状态。 (6)q(6)qf f是终止是终止( (或接受或接受) )状态。状态。 (7)(7)是移动函数。它是从是移动函数。它是从Q Q T Tk k的某一子集映射到的某一子集映射到Q Q (T (T LL，R R，S)S)k k的函数。的函数。 停机状态。停机状态。6 6、TMTM工作原理工作原理设：设： 有穷控制器当前状态是有穷控制器当前状态是q，读读/写头读入当前字写头读入当前字符符
20、a。有穷控制器每步完成以下操作：有穷控制器每步完成以下操作：（1）有穷控制器有穷控制器进入新状态进入新状态q 。（2）根据（根据（q,a)的值，的值，读读/写头写头完成以下操作：完成以下操作： 在当前字符位置上写一个字符在当前字符位置上写一个字符b（b可为可为 )。 左移或右移一个字符位置、或不动。左移或右移一个字符位置、或不动。 仅当有穷控制器所进入新状态仅当有穷控制器所进入新状态p属于停机状态时，属于停机状态时，TM停止操作停止操作注：注：TM的上述操作可能永不停止！的上述操作可能永不停止！7 7、TMTM举例举例DTMDTM程序的一个简单例子程序的一个简单例子TMTM：TMTM的转移函数
21、的转移函数用用表格形式描述。图中说明表格形式描述。图中说明TMTM在输入在输入x=10100x=10100上的上的计算，给出了每一步前后的状态，读写头位置计算，给出了每一步前后的状态，读写头位置以及带的非空白部分的内容以及带的非空白部分的内容 q01bq0(q0,0,R)(q0,1,R)(q1,b,L)q1(q2,b,L)(q3,b,L)(q0,b,S)q2(qf,b,L)(q0,b,S)(q0,b,S)q3(q0,b,S)(q0,b,S)(q0,b,S)转移函数运行运行 b b1 10 01 10 00 0b b b b1 10 01 10 00 0b bb b1 10 01 10 00 0
22、b b b b1 10 01 10 00 0b b b b1 10 01 10 00 0b b b b1 10 01 10 00 0b b b b1 10 01 10 00 0b b b b1 10 01 10 0b bb bq q0 0：q q0 0：q q0 0：q q0 0：q q0 0：q q0 0：q q1 1：q q2 2：q qf f：b b1 10 01 1b bB Bb b8. 8. 图林机接受的语言图林机接受的语言 把把TMTM当作一个语言接受器：当作一个语言接受器：（1 1）将字符串）将字符串x=ax=a1 1a a2 2aan n放在输入带上。在输入带的第一放在输入带上
23、。在输入带的第一个方格中放入符号个方格中放入符号a a1 1，第二个方格中放入符号第二个方格中放入符号a a2 2，第，第n n个方格中放入符号个方格中放入符号a an n。然后在其余方格中放入然后在其余方格中放入b b，其他各其他各带空白带空白。读写头在各带左端第一个方格上。读写头在各带左端第一个方格上。 （2 2）x x被图林机接受：从被图林机接受：从q q0 0开始，经过一系列计算步骤后，开始，经过一系列计算步骤后，最终进入终止状态最终进入终止状态q qf f, , 就说就说TMTM接受字符串接受字符串x x。 （3 3）被图林机被图林机TMTM接受的语言：能被接受的语言：能被TMTM接
24、受的所有字符串的接受的所有字符串的集合。集合。 （4 4）语言）语言L L可被判定：有一个图林机可被判定：有一个图林机M M，使，使L L可被可被M M接受。接受。 （5 5）M M可识别可识别L L：对任何对任何L L中任何中任何x x，M M输出输出x x并停机并停机9.图灵机也可作为计算函数的装置图灵机也可作为计算函数的装置若一个TM总是从输入带前n个方格中读入n个经过编码的字符串x，并且在输出带输出一个整数y（编码后）后停机，那么就说TM计算了函数f(x)=y f(x)=y 例例 数论中的判定向题数论中的判定向题数论中的判定向题：数论中的判定向题：对一个正整数对一个正整数N N，问是否
25、问是否有正整数有正整数m m使得使得N=4mN=4m？在输入时，将整数在输入时，将整数N N表示成二进制形式表示成二进制形式M M放在输放在输入带上，入带上，M M是一个是一个0 0和和1 1的字符串。的字符串。一个正整数可被一个正整数可被4 4整除当且仅当它的二进制整除当且仅当它的二进制表表示的最后二位数字是示的最后二位数字是0，所以可设计一个图林，所以可设计一个图林机机TM对对M的最后二位数字是否为的最后二位数字是否为0进行判别进行判别这个这个TM在标准编码方案下可在标准编码方案下可“解解”“整数可整数可被被4整除性问题整除性问题”1010、图灵机、图灵机TMTM的复杂性的复杂性图灵机图灵
26、机TMTM的的时间复杂性时间复杂性图灵机图灵机TMTM对输入对输入x x的时间复杂性：从初态到终态的的时间复杂性：从初态到终态的计算步数计算步数图灵机图灵机TMTM的时间复杂性的时间复杂性T(n)T(n)：是它处理所有长度为是它处理所有长度为n n的输入所需的最大计算步数。如果对某个长度为的输入所需的最大计算步数。如果对某个长度为n n的输入，图灵机不停机，的输入，图灵机不停机，T(n)T(n)对这个对这个n n值无定义。值无定义。（最坏情况）最坏情况）平均情况：在输入字符串长度为平均情况：在输入字符串长度为n n的情况下，所有的情况下，所有输入上的运行时间的平均值。输入上的运行时间的平均值。
27、图灵机图灵机TMTM的复杂性（续）的复杂性（续）图灵机图灵机TMTM的空间复杂性的空间复杂性图灵机对输入图灵机对输入x x的空间复杂性：计算的空间复杂性：计算x x时，时，k k条条带上所有方格数的总和带上所有方格数的总和图灵机的空间复杂性图灵机的空间复杂性S(n)S(n)是它处理所有长度为是它处理所有长度为n n的输入时，在的输入时，在k k条带上所使用过的方格数的总条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，和。如果某个读写头无限地向右移动而不停机，S(n)S(n)也无定义。也无定义。 TM功能很强大功能很强大许多许多TM能够完成能够完成复杂的工作。虽然复杂的工作。
28、虽然TMTM只有一只有一条（或条（或k k条）连续的带，在每一步也只能完成条）连续的带，在每一步也只能完成非常有限的工作。但是，可以设计出非常有限的工作。但是，可以设计出TMTM完成在完成在普通计算机上能够完成的任何计算，尽管可能普通计算机上能够完成的任何计算，尽管可能要慢得多。要慢得多。1、给定图林机、给定图林机TM M=(Q(Q，T T，I I，B B，q q0 0，q qf f) )Q = q0, q1, q2, q3 , q4 T = a, b, s, t I= a, b 初态初态 q0接受状态接受状态 q4转移函数转移函数 如下边所示：如下边所示： (q0, a)= (q1, s,
29、R) (q0,t )= (q3, t, R) (q1, a)= (q1, a, R) (q1, b)= (q2, t, L) (q1,t )= (q1, t, R) (q2, a)= (q2, a, L) (q2, s)= (q0, s, R) (q2,t )= (q2, t, L) (q3, t)= (q3, t, R) (q3, b)= (q4, b, R)你的任务：作句子你的任务：作句子aabb的计算过程，判定它是否被的计算过程，判定它是否被M接受；接受；abab能被能被M接受吗？你能猜测接受吗？你能猜测M接受的是什么语言？接受的是什么语言？2、设计一个图林机、设计一个图林机TM，使它能
30、识别语言集合使它能识别语言集合习题9.2 P类与NP类问题停机问题停机问题 对于用对于用语言编写的程序语言编写的程序及其一个输入，能及其一个输入，能否设计一个程序，判定否设计一个程序，判定语言程序语言程序相对该相对该输入是否停机？输入是否停机？Church-Turing论题论题“算法算法”的直觉化概念的直觉化概念等于等于 在所有输入上在所有输入上停机停机的的Turing 机机9.2.1 非确定性图灵机非确定性图灵机1 1、确定性图灵机、确定性图灵机确定性图灵机确定性图灵机DTMDTM ： 在图灵机计算模型中，若移动函数在图灵机计算模型中，若移动函数是单值的，是单值的，即即：D D Q Q T
31、Tk kQ Q (T(T LL，R R，S)S)k k是单值的，是单值的，D D是定义域，称这种图灵机为是定义域，称这种图灵机为确定性图灵机确定性图灵机2、非确定性图灵机非确定性图灵机非确定性图灵机非确定性图灵机NDTMNDTM： 一个一个k k带的非确定性图灵机带的非确定性图灵机M M是一个是一个7 7元组：元组： (Q(Q，T T，I I，b b，q q0 0，q qf f) ) 与确定性图灵机不同的是非确定性图灵机允许与确定性图灵机不同的是非确定性图灵机允许移动函数移动函数具有不确定性，即对于具有不确定性，即对于Q Q T Tk k中的每中的每一个值一个值(q;x(q;x1 1,x,x2
32、 2,x xk k) )，当它属于当它属于的定义域的定义域时，时，Q Q (T(T LL，R R，S)S)k k中有惟一的一个中有惟一的一个子集子集(q;x(q;x1 1,x,x2 2,x xk k) )与之对应。与之对应。 运行时可以在运行时可以在(q;x(q;x1 1,x,x2 2,x xk k) )中随意选定一中随意选定一个值作为它的转移。个值作为它的转移。3. 非确定性图林机接受的语言（1 1）x x被非确定性图林机接受，当且仅当，被非确定性图林机接受，当且仅当，存在存在一个计算步骤，一个计算步骤，使从使从q q0 0开始，经过一系列计算开始，经过一系列计算步骤后，最终进入终止状态步骤
33、后，最终进入终止状态q qf f, , 就说就说TMTM接受字接受字符串符串x x。（2 2）被非确定性图林机被非确定性图林机NDTM MNDTM M接受的语言：能接受的语言：能被被NDTMNDTM接受的所有字符串的集合，记作接受的所有字符串的集合，记作L(M)L(M)。4 4、非确定性图灵机的时间复杂性、非确定性图灵机的时间复杂性非确定性图灵机非确定性图灵机NDTMNDTM对输入对输入x x的时间复杂性：的时间复杂性：有计算步骤，从初态到终态的计算步数有计算步骤，从初态到终态的计算步数非确定性图灵机非确定性图灵机NDTMNDTM的时间复杂性的时间复杂性T(n)T(n)：是它是它处理所有长度为
34、处理所有长度为n n的输入的输入x x，有计算步骤，使有计算步骤，使NDTMNDTM接受接受x x，其所需的最大计算步数。如果对其所需的最大计算步数。如果对某个长度为某个长度为n n的输入，图灵机不停机，的输入，图灵机不停机，T(n)T(n)对对这个这个n n值无定义。值无定义。9.2.2 P9.2.2 P类与类与NPNP类语言类语言1、 P类与NP类语言P P类和类和NPNP类语言的定义：类语言的定义： P=L|LP=L|L是一个能在多项式时间内被一台是一个能在多项式时间内被一台DTMDTM所接受的语言所接受的语言 NP=L|L NP=L|L是一个能在多项式时间内被一台是一个能在多项式时间内
35、被一台NDTMNDTM所接受的语言所接受的语言 由于一台确定性图灵机可看作是非确定由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故非确定性图灵机接受。故P P NP NP。 NPP2、非确定性非确定性RAMRAM或或RASMRASM计算模型计算模型在指令系统中加入非确定性选择指令非确定性选择指令Choice(LChoice(L1 1,L,L2 2,L Lk k) ) 其中，其中， L L1 1,L,L2 2,L Lk k是标号是
36、标号在对数耗费下，可用非确定性在对数耗费下，可用非确定性RAMRAM或或RASMRASM计算计算模型定义模型定义NPNP类：类： NP=L|LNP=L|L是一个能在多项式时间内是一个能在多项式时间内被一台非确定性被一台非确定性RAMRAM或或RASMRASM下所接受的语言下所接受的语言 3、计算复杂性理论中的核心问题P=NP？4、非确定性图灵机的操作方式猜测路径（或解、点集）猜测路径（或解、点集）验证路径或解验证路径或解5 5、NPNP类语言举例类语言举例无向图的团问题无向图的团问题该问题的输入是一个有该问题的输入是一个有n n个顶点的无向图个顶点的无向图G=(VG=(V，E)E)和一个整数和
37、一个整数k k。要求判定图要求判定图G G是否包含一个是否包含一个k k顶点的顶点的完全子图完全子图( (团团) )，即判定是否存在即判定是否存在VV V V，|V|=k|V|=k，且对于所有的且对于所有的u u，vVvV，有有(u(u，v)Ev)E。输入的表示：输入的表示：用邻接矩阵表示图用邻接矩阵表示图G G，用二进制串用二进制串表示整数表示整数k k，则团问题的一个实例可用长度为则团问题的一个实例可用长度为n n2 2+(log k)+1+(log k)+1的二进位串表示。的二进位串表示。邻接矩阵中的元素是邻接矩阵中的元素是0 0或或1 1非确定性的图林机非确定性的图林机NDTMNDTM
38、的实现的实现猜测路径（或解、点集）：猜测路径（或解、点集）：用非确定性选择指令选出包含k个顶点的候选顶点子集V验证路径或解：验证路径或解：确定性地检查该子集V是否是团问题的一个解。若V是一个团则接受输入，否则拒绝输入。这显然可以在O(n4)时间内完成。初始化：初始化：算法的第一阶段将输入串w#v分解，并计算出n= ，以及用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就拒绝该输入。显而易见，第一阶段可在 时间内完成。9.2.3 多项式时间验证多项式时间可验证语言类多项式时间可验证语言类VPVP可定义为：可定义为： VP=L|LVP=L|L* *，为一有限字符集，存在一个多项式为一
39、有限字符集，存在一个多项式p p和和一个多项式时间验证算法一个多项式时间验证算法A(XA(X，Y)Y)使得对任意使得对任意XX* *，XLXL当当且仅当存在且仅当存在YY* *，|Y|p(|X|)|Y|p(|X|)且且A(XA(X，Y)=1Y)=1。 XX* *为输入字符串，为输入字符串，YY* *为证书，为证书，A A用用Y Y来证明来证明XL XL ，称，称A A在多项式时间内验证在多项式时间内验证X X定理定理9-19-1：VP=NPVP=NP。 9.3NP完全问题完全问题9.3.1 多项式时间变换1、多项式时间变换定义多项式时间变换定义多项式时间变换定义 设设 ， 是是2 2个语言。所
40、谓语言个语言。所谓语言 能在多项式能在多项式时间内变换为语言时间内变换为语言 ( (简记为简记为 p p ) )是指存在映身是指存在映身f: f: ，且且f f满足：满足： (1)(1)有一个计算有一个计算f f的多项式时间确定性图灵机；的多项式时间确定性图灵机； (2)(2)对于所有对于所有x x ，x x ，当且仅当当且仅当f(x) f(x) 。 L1L2ff f未必是未必是多项式多项式2、NP完全语言类定义定义：定义：语言语言L L是是NPNP完全的完全的当且仅当当且仅当 (1)LNP(1)LNP； (2)(2)对于所有对于所有LNPLNP，有，有L L p p L L。 定义：定义：语
41、言语言L L是是NPNP难的难的，如果语言，如果语言L L满足上述性质满足上述性质(2)(2)，但，但不一定满足性质不一定满足性质(1)(1)定义：所有定义：所有NPNP完全语言构成的语言类称为完全语言构成的语言类称为NPNP完全语言类，完全语言类，记为记为NPCNPC。 NPNPCP3、引理与性质引理引理：若APB，且BP，则AP ABfxf(x)Ng(n)f(x)未必是多项式h(n)性质：（1）APA， （2）若APB，BPC，则APC4、多项式时间变换的有关定理 定理定理9-29-2：设L是NP完全的，即LNPCNPC，则 (1)LP当且仅当PNP； (2)若Lp ，且 NP，则 是NP
42、完全的。 定理定理9-29-2的的(2)(2)可用可用来证明问题的来证明问题的NPNP完完全性。但前提是：全性。但前提是：要有第一个要有第一个NPNP完全完全问题问题L L。NPNP完全语言类完全语言类NPCNPCNPC=CNPC=C：CNPCNP，有，有LNPLNP，且且 LLp pC C 注意注意某个某个L NPCL NPC的条件的条件对某个对某个NPNP完全的完全的L L（即（即LNPCLNPC），），如果如果L L有多项有多项式时间解，那么式时间解，那么 P=NPP=NPNPCNPC类中的问题是类中的问题是NPNP类中最难的问题。类中最难的问题。9.3.2 一些典型的NP完全问题部分NP完全问题树
