什么是NP完全性?

什么是NP完全性?

[拼音]：NP wanquanxing

[外文]：NP-completeness

计算复杂性理论中的一个重要概念，它表征某些问题的固有复杂度。一旦确定一类问题具有NP完全性时，就可知道这类问题实际上是具有相当复杂程度的困难问题。

探讨各种各样问题是否具有NP完全性，研究NP完全问题的处理方法，这对许多实际问题的算法设计和分析很有帮助，并与NP=?P等理论问题密切相关(见非确定性)。人们在这方面开展了大量研究工作，已逐渐形成一个专门性的理论──NP完全性理论。

巡回销售员问题

也称货郎担问题，是一个著名的NP完全问题。假定有一个销售员要到 n个城镇去推销产品，已知各城镇间的距离和一个界限B。问是否有一条旅行路线，恰好通过每个城镇一次，最后回到出发点，且使旅行路线的总长不超过 B。巡回销售员问题实际是一类问题。当对城镇数、城镇间距离和界限 B给定具体数值后，就能得到其中一个具体问题，有时也称作巡回销售员问题的一个“实例”。算法是针对巡回销售员这类问题而言的，即对其中任何实例都应是行之有效的。

P和NP

对于一个问题，如果存在一个图灵机，对这个问题的任何实例，都能给出回答，那么这个问题就称作可解的；如果存在一个图灵机，又存在一介多项式P，在给定问题的实例后（设n是给定实例在0、1编码下的长度)，这个图灵机能在P(n)步内给出回答，那么该问题称作多项式时间可解的。

图灵机可分为确定型和非确定型。确定型图灵机在多项式时间内可解决的全部问题类记作 P。非确定型图灵机在多项式时间内可解决的全部问题类，记作NP。由于确定型机器是非确定型机器的特殊情形，故P吇NP。有趣的是相反的问题:NP吇P?这就是著名的“NP=?P问题”。许多人猜测NP厵P，即在NP中有不是多项式时间可解的问题。在直觉上如果这种问题存在的话，它就是NP中“最难的”问题。NP完全问题就是NP中最难问题的一种形式化。

多项式时间归约

假定给了两个问题类q和q0，如果存在一个确定型图灵机Mq和一个多项式P，对于q中任意一个实例x，Mq都能在P(n)时间内计算出q0中一个实例y(其中n是实例x的编码长度)，使得x是q中有肯定回答的实例，当且仅当y是q0中有肯定回答的实例，我们就说q多项式时间归约到q0。

NP完全问题

对于一个问题q0，如果q0属于NP，且NP中任意一个问题，都能够多项式时间归约到q0，则称q0为NP完全的，或q0具有NP完全性。除巡回销售员问题外，在实践中还发现有大量的NP完全问题，它们来自计算机科学、数学、逻辑学等许多学科领域，总数已超过2000。下面是若干有代表性的NP完全问题。

（1）顶点覆盖问题:给定一个图G＝(V，E)，V为顶点集合，E为边集合，又给定一个正整数K。问V是否有一个子集V′，其顶点数不超过K，并使G中每条边都能被V′覆盖，即每条边的两个顶点中至少有一个在V′中。

（2）三维匹配问题：三个班级，各有K人，共同参加某项活动。活动中，要求三人一组，组中每班一人。三人彼此认识的组称为相识组。假定已知全部可能的相识组，问从中能否选出K个相识组，使得每人能参加且仅能参加一个相识组。

（3）分割问题：给定一堆自然数， 是否能将它们分成两部分，使得这两部分自然数各自的和彼此相等。

（4）带优先次序的调度问题:有m个处理机和一个任务集合，每个任务的执行时间为1，已知任务间的优先次序（不一定每对任务间都有优先次序）和一个截止时间D。问是否有一个m个处理机的调度方法，满足给定的优先次序，且在截止时间D以前结束全部任务。

（5）可满足性问题：对任意给定布尔表达式，是否可对式中各变元赋予真值和假值，使该表达式的值为真。

可满足性问题是历史上第一个NP完全问题，它由S.A.库克于1971年提出。

意义

NP完全性的研究在理论上有重要意义。已经证明，只要有一个NP完全问题属于P，则NP中一切问题都属于P。实际上，NP中任何一个问题都可以多项式时间归约到这个NP完全问题，而该问题又可在多项式时间内解决，故NP中任何问题都可在多项式时间内解决。因此，只要能证明任何一个NP完全问题属于P，就能推出NP=P。这将导致十多年来计算机科学中一个重大问题──“NP=?P问题“的肯定性解决。反之，要否证NP=P，一个明显的方法，就是到NP中去找一个不属于P的问题。作为NP中“最难”问题的NP完全问题，自然是最有希望的候选对象。总之，无论是要证明还是要否证NP=P，NP完全问题的研究，都是很有意义的。

NP完全性的研究在实践中有重要指导作用。在算法设计和分析过程中，如果已证明某问题是NP完全的，这就意味着面临的是一个难于处理的问题。对于它，要找出一个在计算机上可行的（即多项式时间的）算法是十分困难的，甚至可能根本找不到(因为很可能有NP厵P)。因此，对于NP完全问题，最好是去寻找近似解法，或者针对该问题的某些有实用价值的特殊情况，寻找多项式时间算法。

参考书目

M.R.Garey and D.S.Johnson， Computers and Intractability， A Guide to Theory of NP-Completeness，W.H.Freeman and Co.，San Francisco，1979.