当前位置:首页 > 逻辑百科辞典

NP完全问题

设A、B是自然数集,如果存在确定型图灵机多项式时间有界可计算的函数k(x)(即k(x)∈P,参见P=NP问题)使

x∈B 当且仅当 k(x)∈A,

则称B可在多项式时间内归约到A,记作

B≤A

(显然,若B≤A则B≤A)。如果B≤A,就称判定问题“x∈B”可以在多项式时间内归约到判定问题“x∈A”。

设A∈NP(A是非确定型图灵机多项式时间有界可计算的),如果对每个B∈NP都有

B≤A,

则称集合A(判定问题“x∈A”)是NP完全的集合(问题)。

NP完全问题可以看作NP类中最复杂的问题。要证明P=NP,只要证明某个NP完全问题是属于P的就可以了。反之,要证明P≠NP,也只需证明某个NP完全问题不属于P就可以了。

1971年,S.库克发现了第一个NP完全问题,他证明:命题公式的可满足性问题是NP完全的。此后二十年中,人们已经找到了数百个NP完全问题。M.R.加里和D.S.约翰逊所著的《计算机与难解性》一书对NP完全问题作了详尽的叙述,并列举了数百个NP完全问题的实例。(参见P=NP问题。)

声明:本文搜集自网络,观点仅代表作者本人,不代表本站立场。
热门推荐
  • 野史解密
  • 民间故事
  • 幽默故事
  • 童话故事
  • 历史故事
推荐阅读
王冕为何隐居躲名利
王冕为何隐居躲名利
一天,王冕和秦老爹正坐着闲聊,见从外头走进来一个人,头戴皂帽,身穿青布衣服。秦老爹马上立身起来迎接。这人姓翟,是县里的头役,也是买办
刘鹗与甲骨文历史上第一部著录书《铁云藏龟》
刘鹗与甲骨文历史上第一部著录书《铁云藏龟》
您看到展柜中所陈列的线装本书籍是《铁云藏龟》。这本书是“殷墟”甲骨文历史上的第一部著录书,刘鹗辑。 ——中国文字博物馆解说
王翦以重待轻伐楚
王翦以重待轻伐楚
战斗过程中,王翦率大军深入敌境后,不恃强轻敌,不贸然出战,而是筑垒设防,固守示怯,借以麻痹和松懈楚军斗志,创造良好的作战时机。战机一旦
杀手专诸的经济问题
杀手专诸的经济问题
如果把战争和谋杀活动当成一种投资活动,那么专诸的这次谋杀无疑称得上史上回报率最高的一次谋杀。根据血酬定律理论,我们不妨把专诸
苏秦合纵
苏秦合纵
苏秦,东周洛阳人,是与张仪齐名的纵横家。他出身农家,素有大志,到东方的齐国去求学,拜在鬼谷先生的门下学习纵横捭阖之术多年。他学有所
詹天佑修建铁路,詹天佑如何解决技术难题
詹天佑修建铁路,詹天佑如何解决技术难题
詹天佑(1861—1919年),字眷诚,号达朝。广东南海人,居住在湖南省,原籍安徽婺源(今属江西)。中国首位杰出的爱国铁路工程师,负责修建了京张铁