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

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问题。)

声明:本文搜集自网络,观点仅代表作者本人,不代表本站立场。
热门推荐
  • 野史解密
  • 民间故事
  • 幽默故事
  • 童话故事
  • 历史故事
推荐阅读
齐恒公因宽容成就霸业
齐恒公因宽容成就霸业
据传闻齐恒公是因宽容成就了自己的霸业,这是怎么一回事呢?且让我们一探究竟。公元前674年,齐僖公驾崩。太子诸儿(即后来的齐襄公)品质
一鸣惊人,春秋五霸之一楚庄王,曰止戈为武
一鸣惊人,春秋五霸之一楚庄王,曰止戈为武
楚穆王十二年,楚穆王去世,嫡长子熊侣即位,是为楚庄王。楚庄王在令尹成嘉监督与辅佐下,为先君楚穆王发丧。楚庄王即位之初,楚国正处于风
由余是怎样被秦穆公“请”去了秦国
由余是怎样被秦穆公“请”去了秦国
有一次,戎王听说秦穆公贤明,就派由余出使秦国,想要向秦国学习。由余的祖先为晋国人,因避乱才逃到西戎,所以由余能说晋国的话。
秦穆公的“西部大开发”
秦穆公的“西部大开发”
比晋文公稍晚一些时候,秦穆公在西方也建立了自己的霸业(再次提醒,因为秦穆公一直是在西部混,本书就未把他列入春秋五霸)。秦人为嬴姓,本
司马错:司马迁之先祖的军事家与政治家
司马错:司马迁之先祖的军事家与政治家
司马迁在《史记》中明确指出,他的祖先是世袭的史官,从周朝开始就是宫廷史官,司马错更是他的直系祖先。司马错剧照司马错是个神人,他拥
晋穆侯为何讨厌他刚出世的儿子,还给取名叫“记仇”?
晋穆侯为何讨厌他刚出世的儿子,还给取名叫“记仇”?
周宣王死后,太子姬宫湦(sheng)继位,这就是历史上鼎鼎大名的周幽王。从这一刻起,周王朝开始进入了多事之秋,一场又一场的好戏即将开演。