NP完全问题

nullNP完全问题 *NP完全问题 null*1．引言 在前面的各章中，我们对一些算法的设计和分析进行了讨论，这些算法的运行时间可用低次多项式来示（例二次）。在这一章，我们将注意力集中在这样一类问题，这些问题至今没有找到有效算法，而且今后也有可能得知：它们无有效算法。 设П是任意问题，如果对问题存在一个算法，它的时间复杂性是O(nk)，其中n是输入大小，k是非负整数，我们说问题П存在多项式时间算法。现实世界的许多问题并不属于这个范畴，因为求解这些问题需用指数（2n）或超指数（n!）来表示。null* 本章将研究难解问题的一个子类，通常称为NP完全问题（NPC问题）。这一类问题目前约有3000多个，其中还包括数百个著名问题。它们有一个共同特性，如果它们中的一个是多项式可解的话，那么所有其它问题也是多项式可解的。现存的求解这些问题算法的运行时间，对于中等大小的输入也要用几百或几千年的时间。易求解问题： 存在多项式时间算法。 难解问题： （到目前为止）不存在多项式时间算法。null*2．判定问题 为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，我们只考虑一类简单的问题，称为“判定性问题”。也就是说提出一个问题，只需要回答Yes／No的问题。任何一般的最优化问题都可以转化为一系列判定性问题。 例如求图中从A到B的最短路径，该问题可以转化成如下形式： 从A到B是否有长度为1的最短路径？ No 从A到B是否有长度为2的最短路径？ No …………………………………？ No 从A到B是否有长度为k-1的最短路径？ No 从A到B是否有长度为k的最短路径？ Yes 如果问到了k的时候，回答了Yes，则停止发问。我们可以说：从A到B的最短路径长度为k。null*3．确定性算法 定义8.1 设A是求解问题П的一个算法。如果在展示问题П的一个实例时，在整个执行过程中每一步都只有一种选择，则称A是确定性算法。 所以对于同样的输入，实例一遍又一遍地执行，它的输出从不改变。在前面各章所讨论的所有算法都是确定性的。 例1：算法表达式的计算（5+3*8-9） 例2：选择排序法 问题：哈密顿回路 给出一个无向图G=(V,E)，它有哈密顿回路吗？即在图中是否存在一条恰好访问每个顶点一次的回路。 可以用穷举法来求解，一条回路一条回路检查下去，最终便能得到结果。但是穷举法的算法复杂性是指数级的，计算时间随问题规模成指数型增长，很快就变得不可计算了，所以确定性算法对此类问题无效。null*4．P类 定义8.2 判定问题的P类由这样的判定问题组成，它们的Yes／No解可以用确定性算法在多项式时间内得到。例如在O(nk)内得到，其中k是非负整数，n是输入实例的大小。 例1：给出一个有n个整数的表，它们是否按降序排列？ 答：只要检查表中相邻二个数即可，运行时间为O(n)。 例2：给出二个整数集合，它们的交集是否为空？ 答：因集合中无重复元素，先将所有整数排序，然后检查相邻二数是否相等，显然运行时间为 O(nlog2n)。null*5．非确定性算法 有些计算问题是确定性的，例如“加减乘除”，你只要按照推导，按部就班一步步进行，就可以得到结果。但是有些问题无法按部就班直接进行计算的，例如 “找大质数”的问题。已知目前最大质数，那么下一个大质数应该是多少呢？有没有一个公式可以一步步推算出来，显然这样的公式是没有的。 这种问题的，是无法直接计算得到的，只能通过“猜算”来得到结果，这也就是非确定性问题。这些问题通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案、还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，称为非确定性算法。假如“猜算”可以在多项式时间内得到，那么该问题称作“多项式非确定性问题”。null*非确定性算法定义 对于输入x，一个不确定算法由猜测和验证二个阶段组成。 ⑴猜测阶段 在这个阶段产生一个任意字符串y，它可能是对应输入实例x的一个解，也可能不是一个解，甚至不是解的合适形式，也可能在不确定算法的不同次运行中不同。在此阶段，仅仅要求在多项式时间内（O(ni)，n=|x|）产生串y。对于许多问题，这个阶段可以在线性时间内完成。 ⑵验证阶段 检查产生串y是否是解的合适形式，若不是，则算法停下来回答No。 若产生串y是解的合适形式，则继续检查y是否是问题实例x的解。若是，则算法停下来回答Yes；若不是，则算法停下来回答No。在此阶段，也要求在多项式时间内（O(nj)）完成。 非确定性算法的运行时间是猜测阶段和验证阶段所花费时间的和（O(nk)=O(ni)+O(nj)）。null*实例： 求大整数n的一个真因数（即1和大整数n本身以外的一个因数，并且该因数是素数）。 这是一个至今未能找到有效算法的难解问题。对于难解问题，人们除了使用传统型计算方法外，又想出了另一种类型的计算方法，该方法称为非确定性计算。 传说从前有位年轻的国王，想在一天内求出整数 190 334 261 410 902 619 的一个真因素。他用2、3、5、7、11、13、 … …这些素数逐一去试，终于未能算出，于是他把这个问题交给了宰相。国王用的计算方法称为“穷举法”，是一种传统的计算方法，穷举法属“确定性计算方法”。null* 宰相猜想这个数可能是9位整数，于是宰相把全国成年百姓编成十个军，每个军有十个师，每个师有十个旅，每个旅有十个团，每个团有十个营，每个营有十个连，每个连有十个排，每个排有十个班，每个班有十个组，每个组有十个人，于是每个成年百姓都具有一个9位的番号。 然后把题目发下去，让每个成年百姓用自己的番号去除“190334261410902619”这个数，若除尽了就把番号报上去。于是很快就有二个人报上了结果，即“436273009”与“436273291”。经国王验证，这二个整数都是素数，并且这二整数的积就是题目所给的18位整数。null*190 334 261 410 902 619 436 273 009 * 436 273 291军师旅团营连排组人军师旅团营连排组人=这个故事说明算法分析中最基本问题： 求大整数的真因数不能用多项式时间求解，但是验证某数是否是大整数的真因数可以用多项式时间完成，所以求大整数的真因数要比验证大整数的真因数要难得多。 国王用得是确定性计算方法（穷举法），所以计算很快变得无法进行下去；宰相用得是非确定性计算方法，首先猜想，然后验证。null*6．定义8.3 NP类 判定问题的NP类由这样的判定问题组成，对于它们存在多项式时间内运行的不确定性算法。 7．P类和NP类的区别 P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。 NP是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内检查或验证它们的解。 8．NP完全问题 如果一个NP问题的所有可能答案，都可以在多项式时间内进行正确与否验证的话，那么该问题称为“完全多项式非确定性问题”，简称NP完全问题（或NPC问题）。NP完全问题是NP类的一个子类。 null* 前页所述是对“NP完全问题”的一个比较通俗的解释，它避免了很多抽象概念，对于初学者来说较易理解，而NP完全问题在算法分析中有严格定义。 若要证明一个问题∏是NP完全的，仅需证明以下二个条件成立即可。 问题∏是NP问题； 已知问题∏'是一个NP完全问题，问题∏在多项式时间内可归约到问题∏'。 “NP完全问题”可以用穷举法来求解，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度是指数级的，计算的时间随问题的规模成指数型增长，很快便变得不可计算了。 null*哈密顿回路问题（重述）： 给出一个无向图G=(V,E)，它有哈密顿回路吗？即在图中存在一条恰好访问每个顶点一次的回路。 如果给出了哈密顿回路一个答案，我们可以在多项式时间内判断这个答案是否正确。即给出一个任意的回路，我们很容易判断它是否是哈密顿回路，只要看是不是所有的结点都在回路中，并且出现一次就可以了。哈密顿回路问题就是一个NP完全问题。 我们一般认为NP完全问题是难解的问题，因为它们目前不存在一个多项式时间的算法，甚至将来也很难找到，即P≠NP。实际上对于某些顶点数不到100的无向图，利用现有最好的计算机，也需要比较荒唐的时间（例如几百年），才能确定其是否存在一条哈密顿回路。 null* cook在1971年找到了第一个NP完全问题，即可满足性问题（逻辑运算问题），此后人们又陆续发现很多NP完全问题，例如类似哈密顿回路问题（旅行商问题）、图3着色问题、多处理机调度问题等等。 人们发现，所有的NP完全问题都可以在多项式时间内转换到可满足性问题。这样如果它们中的一个存在多项式时间确定性算法的话，那么NP完全问题中的所有问题，都可用多项式时间确定性算法来求解。 人们于是就猜想，既然NP完全问题的所有可能答案，都可以在多项式时间内验证，对于此类问题是否存在一个确定性算法，可以在多项式时间内直接算出或搜寻出正确的答案呢？这就是著名的NP=P？的猜想。这是21世纪计算机科学家向家提出的世界难题。 null* 解决NP=P？的猜想无非两种可能。一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为它们可以转化为同一个问题。 另外的一种可能，就是这样的算法是不存在的，那么就要从数学理论上证明它为什么不存在。 前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，该算法可以在多项式时间内证明某个数是或者不是质数。而在这之前，人们认为质数的证明是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们目前还不知道它的多项式解而已。 null*结 束