第10章_NP完全问题.ppt

《第10章_NP完全问题.ppt》由会员分享，可在线阅读，更多相关《第10章_NP完全问题.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1第第1010章章 NPNP完全问题完全问题 210.1 引言引言10.2 P类类10.3 NP类类10.4 NP完全问题完全问题10.5 co-NP类类(略略)10.6 NPI类类(略略)10.7 四种类之间的关系四种类之间的关系(略略)10.x 近似算法初步近似算法初步310.1 引言引言 在前面的各章中，我们对一些算法的设计和分析进行在前面的各章中，我们对一些算法的设计和分析进行在前面的各章中，我们对一些算法的设计和分析进行在前面的各章中，我们对一些算法的设计和分析进行了讨论，这些算法的运行时间可用低次多项式来表示。了讨论，这些算法的运行时间可用低次多项式来表示。了讨论，这些算法的运行时

2、间可用低次多项式来表示。了讨论，这些算法的运行时间可用低次多项式来表示。在这一章，我们将注意力集中在这样一类问题，这些问在这一章，我们将注意力集中在这样一类问题，这些问在这一章，我们将注意力集中在这样一类问题，这些问在这一章，我们将注意力集中在这样一类问题，这些问题至今没有找到有效算法，而且今后也有可能证明它们题至今没有找到有效算法，而且今后也有可能证明它们题至今没有找到有效算法，而且今后也有可能证明它们题至今没有找到有效算法，而且今后也有可能证明它们不存在有效算法。不存在有效算法。不存在有效算法。不存在有效算法。设设设设是任意问题，如果对该问题存在一个算法，它的是任意问题，如果对该问题存在一

3、个算法，它的是任意问题，如果对该问题存在一个算法，它的是任意问题，如果对该问题存在一个算法，它的时间复杂性是时间复杂性是时间复杂性是时间复杂性是O(nO(nk k)，其中，其中，其中，其中n n是输入大小、是输入大小、是输入大小、是输入大小、k k是非负整数，是非负整数，是非负整数，是非负整数，我们说问题我们说问题我们说问题我们说问题存在多项式时间算法。现实世界的许多问存在多项式时间算法。现实世界的许多问存在多项式时间算法。现实世界的许多问存在多项式时间算法。现实世界的许多问题并不属于这个范畴，因为求解这些问题耗费的时间需题并不属于这个范畴，因为求解这些问题耗费的时间需题并不属于这个范畴，因为

4、求解这些问题耗费的时间需题并不属于这个范畴，因为求解这些问题耗费的时间需用指数函数或阶乘函数来表示。用指数函数或阶乘函数来表示。用指数函数或阶乘函数来表示。用指数函数或阶乘函数来表示。4易求解问题易求解问题 存在多项式时间算法。存在多项式时间算法。难解问题难解问题 到目前为止到目前为止不存在多项式时间算法。不存在多项式时间算法。不存在多项式时间算法。不存在多项式时间算法。本章将研究难解问题的一个子类，通常称为本章将研究难解问题的一个子类，通常称为本章将研究难解问题的一个子类，通常称为本章将研究难解问题的一个子类，通常称为NPNP完全问完全问完全问完全问题题题题(NPC(NPC问题问题问题问题)

5、。这一类问题目前约有。这一类问题目前约有。这一类问题目前约有。这一类问题目前约有30003000多个，其中还多个，其中还多个，其中还多个，其中还包括数百个著名问题。它们有一个共同特性，如果它们包括数百个著名问题。它们有一个共同特性，如果它们包括数百个著名问题。它们有一个共同特性，如果它们包括数百个著名问题。它们有一个共同特性，如果它们中的一个是多项式可解的话，那么所有其它问题也是多中的一个是多项式可解的话，那么所有其它问题也是多中的一个是多项式可解的话，那么所有其它问题也是多中的一个是多项式可解的话，那么所有其它问题也是多项式可解的。现存的求解这些问题算法的运行时间，对项式可解的。现存的求解这

6、些问题算法的运行时间，对项式可解的。现存的求解这些问题算法的运行时间，对项式可解的。现存的求解这些问题算法的运行时间，对于中等大小的输入也要用几百或几千年的时间。于中等大小的输入也要用几百或几千年的时间。于中等大小的输入也要用几百或几千年的时间。于中等大小的输入也要用几百或几千年的时间。5判定问题判定问题判定问题判定问题 为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，我们只考虑一类简单的问题，称为我们只考虑一类简单的问

7、题，称为我们只考虑一类简单的问题，称为我们只考虑一类简单的问题，称为“判定性问题判定性问题判定性问题判定性问题”。也就是说提。也就是说提。也就是说提。也就是说提出一个问题，只需要回答出一个问题，只需要回答出一个问题，只需要回答出一个问题，只需要回答YesYes或者或者或者或者NoNo。任何一般的最优化问题都。任何一般的最优化问题都。任何一般的最优化问题都。任何一般的最优化问题都可以转化为一系列判定性问题。可以转化为一系列判定性问题。可以转化为一系列判定性问题。可以转化为一系列判定性问题。例如，求图中从结点例如，求图中从结点例如，求图中从结点例如，求图中从结点A A到结点到结点到结点到结点B B

8、的最短路径。该问题可以转化成的最短路径。该问题可以转化成的最短路径。该问题可以转化成的最短路径。该问题可以转化成如下形式：如下形式：如下形式：如下形式：uu从从从从A A到到到到B B是否有长度为是否有长度为是否有长度为是否有长度为1 1的最短路径？的最短路径？的最短路径？的最短路径？NoNouu从从从从A A到到到到B B是否有长度为是否有长度为是否有长度为是否有长度为2 2的最短路径？的最短路径？的最短路径？的最短路径？NoNouu？NoNouu从从从从A A到到到到B B是否有长度为是否有长度为是否有长度为是否有长度为k-1k-1的最短路径？的最短路径？的最短路径？的最短路径？NoNou

9、u从从从从A A到到到到B B是否有长度为是否有长度为是否有长度为是否有长度为k k的最短路径？的最短路径？的最短路径？的最短路径？YesYes 如果问到了如果问到了如果问到了如果问到了k k的时候，回答了的时候，回答了的时候，回答了的时候，回答了YesYes，则停止发问。我们可以说，则停止发问。我们可以说，则停止发问。我们可以说，则停止发问。我们可以说，从结点从结点从结点从结点A A到结点到结点到结点到结点B B的最短路径长度为的最短路径长度为的最短路径长度为的最短路径长度为k k。610.2 P类类确定性算法确定性算法确定性算法确定性算法定义定义定义定义10.1(Page 176)10.1

10、(Page 176)设设设设A A是求解问题是求解问题是求解问题是求解问题的一个算法。如果在展示问题的一个算法。如果在展示问题的一个算法。如果在展示问题的一个算法。如果在展示问题的一个实例时，的一个实例时，的一个实例时，的一个实例时，在整个执行过程中每一步都只有一种选择，则称在整个执行过程中每一步都只有一种选择，则称在整个执行过程中每一步都只有一种选择，则称在整个执行过程中每一步都只有一种选择，则称A A是确定性算法。是确定性算法。是确定性算法。是确定性算法。因此对于同样的输入，实例一遍又一遍地执行，它的输出从不改因此对于同样的输入，实例一遍又一遍地执行，它的输出从不改因此对于同样的输入，实例

11、一遍又一遍地执行，它的输出从不改因此对于同样的输入，实例一遍又一遍地执行，它的输出从不改变。变。变。变。在前面各章所讨论的所有算法都是确定性的。给出一个无向图在前面各章所讨论的所有算法都是确定性的。给出一个无向图在前面各章所讨论的所有算法都是确定性的。给出一个无向图在前面各章所讨论的所有算法都是确定性的。给出一个无向图G=(V,E)G=(V,E)，它有哈密顿回路吗？即在图中是否存在一条恰好访问每，它有哈密顿回路吗？即在图中是否存在一条恰好访问每，它有哈密顿回路吗？即在图中是否存在一条恰好访问每，它有哈密顿回路吗？即在图中是否存在一条恰好访问每个结点一次的回路。个结点一次的回路。个结点一次的回路

12、。个结点一次的回路。可以用穷举法来求解，一条回路一条回路检查下去，最终便能可以用穷举法来求解，一条回路一条回路检查下去，最终便能可以用穷举法来求解，一条回路一条回路检查下去，最终便能可以用穷举法来求解，一条回路一条回路检查下去，最终便能得到结果。但是穷举法的算法时间复杂性是指数级的，计算时间得到结果。但是穷举法的算法时间复杂性是指数级的，计算时间得到结果。但是穷举法的算法时间复杂性是指数级的，计算时间得到结果。但是穷举法的算法时间复杂性是指数级的，计算时间随问题规模成指数型增长，问题很快就变得不可计算了，所以确随问题规模成指数型增长，问题很快就变得不可计算了，所以确随问题规模成指数型增长，问题

13、很快就变得不可计算了，所以确随问题规模成指数型增长，问题很快就变得不可计算了，所以确定性算法对此类问题无效。定性算法对此类问题无效。定性算法对此类问题无效。定性算法对此类问题无效。7P类定义类定义定义定义定义定义10.2(Page 176)10.2(Page 176)判定问题的判定问题的判定问题的判定问题的P P类由这样的判定问题组成，它们的类由这样的判定问题组成，它们的类由这样的判定问题组成，它们的类由这样的判定问题组成，它们的Yes/NoYes/No解可以用确定性算法在运行多项式步数内，例如解可以用确定性算法在运行多项式步数内，例如解可以用确定性算法在运行多项式步数内，例如解可以用确定性算

14、法在运行多项式步数内，例如在在在在O(nO(nk k)步内得到，其中步内得到，其中步内得到，其中步内得到，其中k k是某个非负整数，是某个非负整数，是某个非负整数，是某个非负整数，n n是输入大小。是输入大小。是输入大小。是输入大小。例例例例1 1：给出一个有：给出一个有：给出一个有：给出一个有n n个整数的表，它们是否按降序排列？个整数的表，它们是否按降序排列？个整数的表，它们是否按降序排列？个整数的表，它们是否按降序排列？答：只要检查表中相邻二个数即可，运行时间为答：只要检查表中相邻二个数即可，运行时间为答：只要检查表中相邻二个数即可，运行时间为答：只要检查表中相邻二个数即可，运行时间为O

15、(nO(n)。例例例例2 2：给出二个整数集合，它们的交集是否为空？：给出二个整数集合，它们的交集是否为空？：给出二个整数集合，它们的交集是否为空？：给出二个整数集合，它们的交集是否为空？答：先将所有整数排序，然后检查相邻二数是否相等，答：先将所有整数排序，然后检查相邻二数是否相等，答：先将所有整数排序，然后检查相邻二数是否相等，答：先将所有整数排序，然后检查相邻二数是否相等，显然运行时间为显然运行时间为显然运行时间为显然运行时间为 O(nlogO(nlog2 2n)n)。810.3 NP类类 有些计算问题是确定性的，例如有些计算问题是确定性的，例如有些计算问题是确定性的，例如有些计算问题是确

16、定性的，例如“加减乘除加减乘除加减乘除加减乘除”，你只要按照公，你只要按照公，你只要按照公，你只要按照公式推导，按部就班一步步进行，就可以得到结果。但是，有些问式推导，按部就班一步步进行，就可以得到结果。但是，有些问式推导，按部就班一步步进行，就可以得到结果。但是，有些问式推导，按部就班一步步进行，就可以得到结果。但是，有些问题无法按部就班直接进行计算的。例如题无法按部就班直接进行计算的。例如题无法按部就班直接进行计算的。例如题无法按部就班直接进行计算的。例如“找大质数找大质数找大质数找大质数”问题，已知问题，已知问题，已知问题，已知目前最大质数，那么下一个大质数应该是多少呢？有没有一个公目前

17、最大质数，那么下一个大质数应该是多少呢？有没有一个公目前最大质数，那么下一个大质数应该是多少呢？有没有一个公目前最大质数，那么下一个大质数应该是多少呢？有没有一个公式可以一步步推算出来，显然这样的公式是没有的。式可以一步步推算出来，显然这样的公式是没有的。式可以一步步推算出来，显然这样的公式是没有的。式可以一步步推算出来，显然这样的公式是没有的。这种问题的答案，是无法直接计算得到的，只能通过这种问题的答案，是无法直接计算得到的，只能通过这种问题的答案，是无法直接计算得到的，只能通过这种问题的答案，是无法直接计算得到的，只能通过“猜算猜算猜算猜算”来得到结果，这就是非确定性问题。这些问题通常有个

18、算法，它来得到结果，这就是非确定性问题。这些问题通常有个算法，它来得到结果，这就是非确定性问题。这些问题通常有个算法，它来得到结果，这就是非确定性问题。这些问题通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的还是错误的。这个可以告诉你正确的还是错误的。这个可以告诉你正确的还是错误的。这个可以告诉你正确的还是错误的。这个可以告诉你“猜算猜算猜算猜算”的答案正确与否的的答案正确与否的的答案正确与否的的答

19、案正确与否的算法，称为非确定性算法。假如算法，称为非确定性算法。假如算法，称为非确定性算法。假如算法，称为非确定性算法。假如“猜算猜算猜算猜算”可以在多项式时间内得可以在多项式时间内得可以在多项式时间内得可以在多项式时间内得到，那么该问题称作到，那么该问题称作到，那么该问题称作到，那么该问题称作“多项式非确定性问题多项式非确定性问题多项式非确定性问题多项式非确定性问题”。9非确定性算法非确定性算法非确定性算法非确定性算法 对于输入对于输入对于输入对于输入x x，一个非确定性算法由猜测和验证二个阶段组成。，一个非确定性算法由猜测和验证二个阶段组成。，一个非确定性算法由猜测和验证二个阶段组成。，一

20、个非确定性算法由猜测和验证二个阶段组成。猜测阶段猜测阶段猜测阶段猜测阶段 在这个阶段产生一个任意字符串在这个阶段产生一个任意字符串在这个阶段产生一个任意字符串在这个阶段产生一个任意字符串y y，它可能对应输入实例的一，它可能对应输入实例的一，它可能对应输入实例的一，它可能对应输入实例的一个解，也可以不对应解。事实上，它甚至可能不是所求解的合适个解，也可以不对应解。事实上，它甚至可能不是所求解的合适个解，也可以不对应解。事实上，它甚至可能不是所求解的合适个解，也可以不对应解。事实上，它甚至可能不是所求解的合适形式，它可能在非确定算法的不同次运行中不同。它仅要求在多形式，它可能在非确定算法的不同次

21、运行中不同。它仅要求在多形式，它可能在非确定算法的不同次运行中不同。它仅要求在多形式，它可能在非确定算法的不同次运行中不同。它仅要求在多项式步数内产生这个串，即在项式步数内产生这个串，即在项式步数内产生这个串，即在项式步数内产生这个串，即在O(nO(ni i)时间内，这里时间内，这里时间内，这里时间内，这里n=n=|x x|，i i是非负是非负是非负是非负整数整数整数整数。对于许多问题，这一阶段可以在线性时间内完成。对于许多问题，这一阶段可以在线性时间内完成。对于许多问题，这一阶段可以在线性时间内完成。对于许多问题，这一阶段可以在线性时间内完成。验证阶段验证阶段验证阶段验证阶段 首先检查产生的

22、解串首先检查产生的解串首先检查产生的解串首先检查产生的解串y y是否有合适的形式，如果不是，则算法是否有合适的形式，如果不是，则算法是否有合适的形式，如果不是，则算法是否有合适的形式，如果不是，则算法停下来并回答停下来并回答停下来并回答停下来并回答NoNo；如果；如果；如果；如果y y是合适形式，那么算法继续检查它是否是合适形式，那么算法继续检查它是否是合适形式，那么算法继续检查它是否是合适形式，那么算法继续检查它是否是问题实例是问题实例是问题实例是问题实例x x的解。若是，则算法停下来并回答的解。若是，则算法停下来并回答的解。若是，则算法停下来并回答的解。若是，则算法停下来并回答YesYes

23、；否则算法停；否则算法停；否则算法停；否则算法停下来并回答下来并回答下来并回答下来并回答NoNo。我们也要求这个阶段在多项式步数内完成，即在。我们也要求这个阶段在多项式步数内完成，即在。我们也要求这个阶段在多项式步数内完成，即在。我们也要求这个阶段在多项式步数内完成，即在OO(n(nj j)时间内，这里时间内，这里时间内，这里时间内，这里j j是一个非负整数。是一个非负整数。是一个非负整数。是一个非负整数。非确定性算法的运行时间是由猜测阶段和验证阶段二部分耗费非确定性算法的运行时间是由猜测阶段和验证阶段二部分耗费非确定性算法的运行时间是由猜测阶段和验证阶段二部分耗费非确定性算法的运行时间是由猜

24、测阶段和验证阶段二部分耗费时间组成，因此它是时间组成，因此它是时间组成，因此它是时间组成，因此它是O(nO(nk k)=)=O(nO(ni i)+O(n)+O(nj j)，k k是某个非负整数。是某个非负整数。是某个非负整数。是某个非负整数。10 例：求大整数例：求大整数例：求大整数例：求大整数n n的一个真因数的一个真因数的一个真因数的一个真因数(即即即即1 1和和和和n n本身以外的一个本身以外的一个本身以外的一个本身以外的一个因数，并且该因数是素数因数，并且该因数是素数因数，并且该因数是素数因数，并且该因数是素数)。这是一个至今未能找到有效算法的难解问题。对于难这是一个至今未能找到有效算

25、法的难解问题。对于难这是一个至今未能找到有效算法的难解问题。对于难这是一个至今未能找到有效算法的难解问题。对于难解问题，人们除了使用传统型计算方法外，又想出了另解问题，人们除了使用传统型计算方法外，又想出了另解问题，人们除了使用传统型计算方法外，又想出了另解问题，人们除了使用传统型计算方法外，又想出了另一种类型的计算方法，该方法称为一种类型的计算方法，该方法称为一种类型的计算方法，该方法称为一种类型的计算方法，该方法称为“非确定性算法非确定性算法非确定性算法非确定性算法”。传说从前有位年轻的国王，想求出整数传说从前有位年轻的国王，想求出整数传说从前有位年轻的国王，想求出整数传说从前有位年轻的国

26、王，想求出整数190 334 261 410 902 619的一个真因素。他用的一个真因素。他用的一个真因素。他用的一个真因素。他用2 2、3 3、5 5、7 7、1111、1313、这些素这些素这些素这些素数逐一去试，化了九牛二虎之力也无法算出，于是他把数逐一去试，化了九牛二虎之力也无法算出，于是他把数逐一去试，化了九牛二虎之力也无法算出，于是他把数逐一去试，化了九牛二虎之力也无法算出，于是他把这个问题交给了宰相。国王用的计算方法称为这个问题交给了宰相。国王用的计算方法称为这个问题交给了宰相。国王用的计算方法称为这个问题交给了宰相。国王用的计算方法称为“穷举法穷举法穷举法穷举法”，是一种传统

27、的计算方法，穷举法属，是一种传统的计算方法，穷举法属，是一种传统的计算方法，穷举法属，是一种传统的计算方法，穷举法属“确定性算法确定性算法确定性算法确定性算法”。11 宰相猜想这个数可能是宰相猜想这个数可能是宰相猜想这个数可能是宰相猜想这个数可能是9 9位整数，于是宰相把全国成年位整数，于是宰相把全国成年位整数，于是宰相把全国成年位整数，于是宰相把全国成年百姓编成十个军，每个军有十个师，每个师有十个旅，百姓编成十个军，每个军有十个师，每个师有十个旅，百姓编成十个军，每个军有十个师，每个师有十个旅，百姓编成十个军，每个军有十个师，每个师有十个旅，每个旅有十个团，每个团有十个营，每个营有十个连，每

28、个旅有十个团，每个团有十个营，每个营有十个连，每个旅有十个团，每个团有十个营，每个营有十个连，每个旅有十个团，每个团有十个营，每个营有十个连，每个连有十个排，每个排有十个班，每个班有十个组，每个连有十个排，每个排有十个班，每个班有十个组，每个连有十个排，每个排有十个班，每个班有十个组，每个连有十个排，每个排有十个班，每个班有十个组，每个组有十个人，于是每个成年百姓都具有一个每个组有十个人，于是每个成年百姓都具有一个每个组有十个人，于是每个成年百姓都具有一个每个组有十个人，于是每个成年百姓都具有一个9 9位的番位的番位的番位的番号。号。号。号。然后把题目发下去，让每个成年百姓用自己的番号去然后把

29、题目发下去，让每个成年百姓用自己的番号去然后把题目发下去，让每个成年百姓用自己的番号去然后把题目发下去，让每个成年百姓用自己的番号去除除除除“190334261410902619”190334261410902619”这个数，若除尽了就把番号这个数，若除尽了就把番号这个数，若除尽了就把番号这个数，若除尽了就把番号报上来。报上来。报上来。报上来。很快就有二个人报上了结果，即很快就有二个人报上了结果，即很快就有二个人报上了结果，即很快就有二个人报上了结果，即“436273009”436273009”与与与与“436273291”436273291”。经国王验证，这二个整数都是素数，并。经国王验证，

30、这二个整数都是素数，并。经国王验证，这二个整数都是素数，并。经国王验证，这二个整数都是素数，并且这二个整数的积就是题目所给的且这二个整数的积就是题目所给的且这二个整数的积就是题目所给的且这二个整数的积就是题目所给的1818位整数。位整数。位整数。位整数。12190 334 261 410 902 619 436 273 009*436 273 291军军军军 师师师师 旅旅旅旅团团团团 营营营营 连连连连排排排排 组组组组 人人人人军军军军 师师师师 旅旅旅旅团团团团 营营营营 连连连连排排排排 组组组组 人人人人 =这个故事说明算法分析中最基本问题：这个故事说明算法分析中最基本问题：这个故事

31、说明算法分析中最基本问题：这个故事说明算法分析中最基本问题：u求大整数的真因数不能用多项式时间求解，但是验证求大整数的真因数不能用多项式时间求解，但是验证求大整数的真因数不能用多项式时间求解，但是验证求大整数的真因数不能用多项式时间求解，但是验证某数是否是大整数的真因数可以用多项式时间完成。所某数是否是大整数的真因数可以用多项式时间完成。所某数是否是大整数的真因数可以用多项式时间完成。所某数是否是大整数的真因数可以用多项式时间完成。所以，求大整数的真因数要比验证真因数要难得多；以，求大整数的真因数要比验证真因数要难得多；以，求大整数的真因数要比验证真因数要难得多；以，求大整数的真因数要比验证真

32、因数要难得多；u国王用得是确定性计算方法国王用得是确定性计算方法国王用得是确定性计算方法国王用得是确定性计算方法(穷举法穷举法穷举法穷举法)，所以计算很快变，所以计算很快变，所以计算很快变，所以计算很快变得无法进行下去；宰相用得是非确定性计算方法，首先得无法进行下去；宰相用得是非确定性计算方法，首先得无法进行下去；宰相用得是非确定性计算方法，首先得无法进行下去；宰相用得是非确定性计算方法，首先猜想，然后验证。猜想，然后验证。猜想，然后验证。猜想，然后验证。13NP类定义类定义定义定义10.3(Page 177)NP类类是由这样的判定问题组成：对于它们存在是由这样的判定问题组成：对于它们存在多项

33、式时间内运行的非确定性算法。多项式时间内运行的非确定性算法。P类和类和NP类的区别类的区别uP类是一个判定问题类，这些问题可以用一个类是一个判定问题类，这些问题可以用一个确定性算法，在多项式时间内判定或解出；确定性算法，在多项式时间内判定或解出；uNP类是一个判定问题类，这些问题可以用一个类是一个判定问题类，这些问题可以用一个确定性算法，在多项式时间内检查或验证它们的确定性算法，在多项式时间内检查或验证它们的解。解。1410.4 NP完全问题完全问题定义定义定义定义10.4(Page 178)10.4(Page 178)设设设设和和和和 是二个判定问题。如果存在一个确定性算法是二个判定问题。如

34、果存在一个确定性算法是二个判定问题。如果存在一个确定性算法是二个判定问题。如果存在一个确定性算法A A，它的，它的，它的，它的行为如下：当给行为如下：当给行为如下：当给行为如下：当给A A展示问题展示问题展示问题展示问题的一个实例的一个实例的一个实例的一个实例I I，算法，算法，算法，算法A A可以把它变换可以把它变换可以把它变换可以把它变换为问题为问题为问题为问题 的实例的实例的实例的实例I I。当且仅当对。当且仅当对。当且仅当对。当且仅当对I I 回答回答回答回答yesyes时，对时，对时，对时，对I I回答回答回答回答YesYes，而且这，而且这，而且这，而且这个变换在多项式时间内完成。

35、那么我们说个变换在多项式时间内完成。那么我们说个变换在多项式时间内完成。那么我们说个变换在多项式时间内完成。那么我们说可以在多项式时间内可以在多项式时间内可以在多项式时间内可以在多项式时间内归约到归约到归约到归约到，用符号，用符号，用符号，用符号polypoly 表示。表示。表示。表示。定理定理定理定理10.3(Page 178)10.3(Page 178)设设设设、和和和和 是三个判定问题，有是三个判定问题，有是三个判定问题，有是三个判定问题，有polypoly 和和和和 polypoly，那么，那么，那么，那么polypoly。推论推论推论推论10.1(Page 179)10.1(Page

36、 179)如果如果如果如果和和和和 是是是是NPNP中的二个问题，若有中的二个问题，若有中的二个问题，若有中的二个问题，若有 polypoly，并且，并且，并且，并且 是完全是完全是完全是完全的，则的，则的，则的，则是完全的。是完全的。是完全的。是完全的。15 如果一个如果一个如果一个如果一个NPNP问题的所有可能答案，都可以在多项式时间内进行问题的所有可能答案，都可以在多项式时间内进行问题的所有可能答案，都可以在多项式时间内进行问题的所有可能答案，都可以在多项式时间内进行正确与否验证的话，那么该问题称为正确与否验证的话，那么该问题称为正确与否验证的话，那么该问题称为正确与否验证的话，那么该问

37、题称为“完全多项式非确定性问题完全多项式非确定性问题完全多项式非确定性问题完全多项式非确定性问题”，简称，简称，简称，简称NPNP完全问题或完全问题或完全问题或完全问题或NPCNPC问题。问题。问题。问题。NPNP完全问题是完全问题是完全问题是完全问题是NPNP类的一个子类的一个子类的一个子类的一个子类。类。类。类。这是对这是对这是对这是对“NPNP完全问题完全问题完全问题完全问题”的一个比较通俗的解释，对于初学者来的一个比较通俗的解释，对于初学者来的一个比较通俗的解释，对于初学者来的一个比较通俗的解释，对于初学者来说比较容易理解，上页则给出了说比较容易理解，上页则给出了说比较容易理解，上页则

38、给出了说比较容易理解，上页则给出了“NPNP完全问题完全问题完全问题完全问题”的严格定义。的严格定义。的严格定义。的严格定义。例例例例10.5 10.5 考虑下面二个问题考虑下面二个问题考虑下面二个问题考虑下面二个问题(Page 179)(Page 179)哈密顿回路问题：哈密顿回路问题：哈密顿回路问题：哈密顿回路问题：给出一个无向图给出一个无向图给出一个无向图给出一个无向图G=(V,E)G=(V,E)，它有哈密顿回路吗，它有哈密顿回路吗，它有哈密顿回路吗，它有哈密顿回路吗？即在图中存在一条恰好访问每个结点一次的回路。？即在图中存在一条恰好访问每个结点一次的回路。？即在图中存在一条恰好访问每个

39、结点一次的回路。？即在图中存在一条恰好访问每个结点一次的回路。旅行商问题：给出一个旅行商问题：给出一个旅行商问题：给出一个旅行商问题：给出一个n n个城市集合，且给出城市间的距离。对个城市集合，且给出城市间的距离。对个城市集合，且给出城市间的距离。对个城市集合，且给出城市间的距离。对于一个整数于一个整数于一个整数于一个整数k k，是否存在最长为，是否存在最长为，是否存在最长为，是否存在最长为k k的游程？这里，一条游程是一个的游程？这里，一条游程是一个的游程？这里，一条游程是一个的游程？这里，一条游程是一个回路，它恰好访问每个城市一次。回路，它恰好访问每个城市一次。回路，它恰好访问每个城市一次

40、。回路，它恰好访问每个城市一次。众所周知，哈密顿回路问题是众所周知，哈密顿回路问题是众所周知，哈密顿回路问题是众所周知，哈密顿回路问题是NPCNPC问题。根据这一事实我们来问题。根据这一事实我们来问题。根据这一事实我们来问题。根据这一事实我们来证明旅行商问题也是证明旅行商问题也是证明旅行商问题也是证明旅行商问题也是NPCNPC问题。问题。问题。问题。16证明：旅行商问题是证明：旅行商问题是证明：旅行商问题是证明：旅行商问题是NPNP问题问题问题问题 使用非确定性算法，先猜测一个城市序列，然后验证这个序列使用非确定性算法，先猜测一个城市序列，然后验证这个序列使用非确定性算法，先猜测一个城市序列，

41、然后验证这个序列使用非确定性算法，先猜测一个城市序列，然后验证这个序列是一个游程。如果是，只要判断游程的长度是否超过界是一个游程。如果是，只要判断游程的长度是否超过界是一个游程。如果是，只要判断游程的长度是否超过界是一个游程。如果是，只要判断游程的长度是否超过界k k即可。即可。即可。即可。证明：哈密顿回路问题在多项式时间内归约到旅行商问题证明：哈密顿回路问题在多项式时间内归约到旅行商问题证明：哈密顿回路问题在多项式时间内归约到旅行商问题证明：哈密顿回路问题在多项式时间内归约到旅行商问题 设设设设GG是哈密顿回路的任意实例。我们构建一个含权图是哈密顿回路的任意实例。我们构建一个含权图是哈密顿回

42、路的任意实例。我们构建一个含权图是哈密顿回路的任意实例。我们构建一个含权图GG 和一个界和一个界和一个界和一个界k k，使得当且仅当，使得当且仅当，使得当且仅当，使得当且仅当GG 有一个总长不超过有一个总长不超过有一个总长不超过有一个总长不超过k k的游程时，的游程时，的游程时，的游程时，GG有一条哈密顿有一条哈密顿有一条哈密顿有一条哈密顿回路。回路。回路。回路。设设设设G=(V,E)G=(V,E)，GG=(V,E=(V,E)是结点是结点是结点是结点V V集合上的完全图，即集合上的完全图，即集合上的完全图，即集合上的完全图，即E=(u,v)|u,vE=(u,v)|u,vVV 给给给给E E 中

43、的每条边的长度定义如下：中的每条边的长度定义如下：中的每条边的长度定义如下：中的每条边的长度定义如下：其中其中其中其中n=|V|n=|V|，且指派，且指派，且指派，且指派k=nk=n。从构建中可以看到，当且仅当从构建中可以看到，当且仅当从构建中可以看到，当且仅当从构建中可以看到，当且仅当GG 有一个长度恰好为有一个长度恰好为有一个长度恰好为有一个长度恰好为n n的游程时，的游程时，的游程时，的游程时，GG有一条哈密顿回路。有一条哈密顿回路。有一条哈密顿回路。有一条哈密顿回路。由此可得：由此可得：由此可得：由此可得：哈密顿回路问题哈密顿回路问题哈密顿回路问题哈密顿回路问题polypoly旅行商问

44、题旅行商问题旅行商问题旅行商问题17 NPC NPC问题可以用穷举法来求解，对于可能解一个个检问题可以用穷举法来求解，对于可能解一个个检问题可以用穷举法来求解，对于可能解一个个检问题可以用穷举法来求解，对于可能解一个个检查下去，最终便能得到结果。但是随着问题规模增大，查下去，最终便能得到结果。但是随着问题规模增大，查下去，最终便能得到结果。但是随着问题规模增大，查下去，最终便能得到结果。但是随着问题规模增大，计算时间成指数型增长，很快变得不可计算了。计算时间成指数型增长，很快变得不可计算了。计算时间成指数型增长，很快变得不可计算了。计算时间成指数型增长，很快变得不可计算了。如果给出一个回路，我

45、们很容易判断它是否是哈密顿如果给出一个回路，我们很容易判断它是否是哈密顿如果给出一个回路，我们很容易判断它是否是哈密顿如果给出一个回路，我们很容易判断它是否是哈密顿回路。只要检查所有的结点是否都在这个回路中，并且回路。只要检查所有的结点是否都在这个回路中，并且回路。只要检查所有的结点是否都在这个回路中，并且回路。只要检查所有的结点是否都在这个回路中，并且只出现一次。检查仅需只出现一次。检查仅需只出现一次。检查仅需只出现一次。检查仅需O(nO(n2 2)时间。时间。时间。时间。我们一般认为我们一般认为我们一般认为我们一般认为NPCNPC问题是难解问题。因为到目前为止，问题是难解问题。因为到目前为

46、止，问题是难解问题。因为到目前为止，问题是难解问题。因为到目前为止，它们它们它们它们还不存在一个多项式时间的算法，甚至将来也很难还不存在一个多项式时间的算法，甚至将来也很难还不存在一个多项式时间的算法，甚至将来也很难还不存在一个多项式时间的算法，甚至将来也很难找到，即找到，即找到，即找到，即PNPPNP。实际上，对于某些结点数不到。实际上，对于某些结点数不到。实际上，对于某些结点数不到。实际上，对于某些结点数不到100100的无的无的无的无向图，使用现有速度最快的计算机也需要比较荒唐的时向图，使用现有速度最快的计算机也需要比较荒唐的时向图，使用现有速度最快的计算机也需要比较荒唐的时向图，使用现

47、有速度最快的计算机也需要比较荒唐的时间，例如耗费几百年才能够确定它是否存在一条哈密顿间，例如耗费几百年才能够确定它是否存在一条哈密顿间，例如耗费几百年才能够确定它是否存在一条哈密顿间，例如耗费几百年才能够确定它是否存在一条哈密顿回路。回路。回路。回路。18 库克在库克在库克在库克在19711971年找到了第一个年找到了第一个年找到了第一个年找到了第一个NPNP完全问题，即可满足性完全问题，即可满足性完全问题，即可满足性完全问题，即可满足性问题问题问题问题(逻辑运算问题逻辑运算问题逻辑运算问题逻辑运算问题)。此后，人们又陆续发现很多。此后，人们又陆续发现很多。此后，人们又陆续发现很多。此后，人们

48、又陆续发现很多NPNP完完完完全问题。例如，哈密顿回路问题、旅行商问题、图的全问题。例如，哈密顿回路问题、旅行商问题、图的全问题。例如，哈密顿回路问题、旅行商问题、图的全问题。例如，哈密顿回路问题、旅行商问题、图的3 3着色问题、多处理机调度问题、着色问题、多处理机调度问题、着色问题、多处理机调度问题、着色问题、多处理机调度问题、。人们发现，所有的人们发现，所有的人们发现，所有的人们发现，所有的NPNP完全问题都可以在多项式时间内完全问题都可以在多项式时间内完全问题都可以在多项式时间内完全问题都可以在多项式时间内转换到可满足性问题。只要它们中的一个，转换到可满足性问题。只要它们中的一个，转换到

49、可满足性问题。只要它们中的一个，转换到可满足性问题。只要它们中的一个，如果如果如果如果存在存在存在存在“多项式时间确定性算法多项式时间确定性算法多项式时间确定性算法多项式时间确定性算法”的话，那么的话，那么的话，那么的话，那么NPCNPC问题中的所有问题中的所有问题中的所有问题中的所有问题，都可以用问题，都可以用问题，都可以用问题，都可以用“多项式时间确定性算法多项式时间确定性算法多项式时间确定性算法多项式时间确定性算法”来求解。来求解。来求解。来求解。人们于是就猜想，既然人们于是就猜想，既然人们于是就猜想，既然人们于是就猜想，既然NPCNPC问题的所有可能解，都可问题的所有可能解，都可问题的

50、所有可能解，都可问题的所有可能解，都可以在多项式时间内验证，对于此类问题是否存在一个确以在多项式时间内验证，对于此类问题是否存在一个确以在多项式时间内验证，对于此类问题是否存在一个确以在多项式时间内验证，对于此类问题是否存在一个确定性算法，可以在多项式时间内直接给出解呢？这就是定性算法，可以在多项式时间内直接给出解呢？这就是定性算法，可以在多项式时间内直接给出解呢？这就是定性算法，可以在多项式时间内直接给出解呢？这就是著名的著名的著名的著名的NPNP=P?P?的猜想。这是的猜想。这是的猜想。这是的猜想。这是2121世纪计算机科学家向数学世纪计算机科学家向数学世纪计算机科学家向数学世纪计算机科学