1) NP-completeness
NP-完全性
1.
For the subclasses LCNF≥k of LCNF, in which formulas have only clauses of length at least k, the NP-completeness of the decision problem LSAT≥k is closely relevant to whether or not ther.
LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关。
2) NP-completeness
NP完全性
3) NP complete
NP完全
1.
The relationship between discrete computational models and continuous models and the computational power of the Turing machine are discussed, and the definitions of the NP complete problem are generalized in the paper.
本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及 NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形 Packing问题进行了有益的探讨。
2.
Presented a formal model for Web services composition problem(WSC) and proved that WSC is NP complete.
本文对服务组合问题进行规划建模,证明了该问题是NP完全的,提出了一种基于图的自动组合方法ASC-Graph,ASC-Graph分为组合规划图构造阶段和组合解搜索阶段。
5) NP-complete
NP-完全
1.
The NP-completeness of The Path Chromatic Number Problem of Graphs;
图的路色数问题的NP－完全性
2.
2-Induced-Matching Partition Problem and 2-Induced-Matching Cover Problem of Graphs with Diameter 5 are NP-complete
直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性(英文)
补充资料：NP完全性
计算复杂性理论中的一个重要概念，它表征某些问题的固有复杂度。一旦确定一类问题具有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完全问题。
① 顶点覆盖问题:给定一个图G＝(V，E),V为顶点集合,E为边集合，又给定一个正整数K。问V是否有一个子集V′,其顶点数不超过K，并使G中每条边都能被V′覆盖，即每条边的两个顶点中至少有一个在V′中。
② 三维匹配问题：三个班级，各有K人,共同参加某项活动。活动中，要求三人一组，组中每班一人。三人彼此认识的组称为相识组。假定已知全部可能的相识组,问从中能否选出K个相识组，使得每人能参加且仅能参加一个相识组。
③ 分割问题：给定一堆自然数, 是否能将它们分成两部分，使得这两部分自然数各自的和彼此相等。
④ 带优先次序的调度问题:有m个处理机和一个任务集合，每个任务的执行时间为1,已知任务间的优先次序（不一定每对任务间都有优先次序）和一个截止时间D。问是否有一个m个处理机的调度方法，满足给定的优先次序，且在截止时间D以前结束全部任务。
⑤ 可满足性问题：对任意给定布尔表达式，是否可对式中各变元赋予真值和假值，使该表达式的值为真。
可满足性问题是历史上第一个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.
探讨各种各样问题是否具有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完全问题。
① 顶点覆盖问题:给定一个图G＝(V，E),V为顶点集合,E为边集合，又给定一个正整数K。问V是否有一个子集V′,其顶点数不超过K，并使G中每条边都能被V′覆盖，即每条边的两个顶点中至少有一个在V′中。
② 三维匹配问题：三个班级，各有K人,共同参加某项活动。活动中，要求三人一组，组中每班一人。三人彼此认识的组称为相识组。假定已知全部可能的相识组,问从中能否选出K个相识组，使得每人能参加且仅能参加一个相识组。
③ 分割问题：给定一堆自然数, 是否能将它们分成两部分，使得这两部分自然数各自的和彼此相等。
④ 带优先次序的调度问题:有m个处理机和一个任务集合，每个任务的执行时间为1,已知任务间的优先次序（不一定每对任务间都有优先次序）和一个截止时间D。问是否有一个m个处理机的调度方法，满足给定的优先次序，且在截止时间D以前结束全部任务。
⑤ 可满足性问题：对任意给定布尔表达式，是否可对式中各变元赋予真值和假值，使该表达式的值为真。
可满足性问题是历史上第一个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.
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条