1) 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-完全性(英文)
3) NP complete
NP-完全
1.
It is proved that the problem is NP complete.
建立了多参数最小支撑树问题 (RMST)的模型 ,并证明该问题是 NP-完全的。
4) 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分为组合规划图构造阶段和组合解搜索阶段。
6) 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中是否含有不可满足公式密切相关。
补充资料：NP完全性理论
NP完全性理论
theory of NP completeness
NP WQnquQnxing 11}unNP完全性理论(th即ry of NP completeness) 研究NP完全间题的理论。一个问题被确认为具有NP完全性，或被称为是NP完全问题，意味着该问题是NP问题类中“最困难”的问题，是一个固有难解问题。对于这种问题，寻求一个现实可计算的(即多项式时间的)算法，是十分困难的，甚至可能是根本不存在的。历史上第一个NP完全问题是可满足性问题，它是由S.A.G刀k于 1971年提出的。下面是一个常被人们提起的NP完全问题。 旅行商间题也称货郎担问题。假定一个销售员要到n个城市去推销产品。已知各城市间路程d，，，(l(泛，](n)和一个界限B，问是否有一条旅行路线，恰好到每个城市一次，最后返回出发城市，且总路程不超过B? 旅行商问题还有另一种提法:试求出总路程最短的旅行路线。前者称为判定形式问题，后者称为最优形式问题。可以证明两种形式问题在下述意义下是等价的:如果对于最优形式问题有多项式时间算法，那么也容易找到对于判定形式问题的多项式时间算法，反之亦然。同时还容易看出，问题可以看成由无数个实例组成，一组n，B和d‘，，，就代表了问题的一个实例。算法必须对问题的一切实例都能给出解答。 对于旅行商问题，从一个城市出发，有n一1个城市可作为第二站，选定一个城市后，又有n一2个城市可作为第三站，……。这样，总共将有(n一1)!条不同的旅行路线。检查每一条旅行路线的总路程，就可以得到问题的解答。但这是一个指数时间复杂度的算法。指数时间算法被公认为不是现实可计算的算法。实际上，对一个底数为2的指数时间算法，当n为50时，即使采用每秒百万次运算的计算机，要计算出解答来，也需要35.7年;而当n为60时，则需要366个世纪，这是人们绝对无法容忍的。 一般Nl〕完全问题，情况都与旅行商间题相似，都有一个比较明显的指数时间算法。多项式时间算法被公认为现实可计算的算法，那么NP完全问题是否有多项式时间算法?这是Nl〕完全性理论中的核心问题。 P一类问题的集合。对类中任一问题，都存在一个确定型图灵机M和一个多项式P，对于该问题的任何(编码)长度为n的实例，M都能在P(n)步内，给出对这个实例的回答(参见P类问题)。 NP一类问题的集合。对类中任一问题，都存在一个非确定型图灵机M和一个多项式P，对于该问题的任何长度为n的实例，M都能在P(n)步内，给出对这个实例的回答(参见NP类问题)。
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条