[拼音]: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.