补充资料：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类问题)。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。