出处：数理化力学卷 • 数 学 • 运筹学 • 组合数学 • 拉丁方
| 词条 | NP完全问题 |
| 释义 | NP完全问题 NP完全问题 简称“NPC问题”。具有如下共性的一类NP问题:(1)类中每一个问题都还未找到多项式算法;(2)若类中有一个问题是P问题,则类中所有问题都是P问题。NP完全问题由库克(S.A.Cook)于1971年给出,至今已有近千个问题属于此类,包括哈密顿圈问题、0-1背包问题等许多著名问题,人们越来越相信NPC问题不是P问题。2000年5月法国克莱(Clay)数学研究所悬赏解决七个千禧年数学难题,其中第一个问题就是NPC=P? 出处：数理化力学卷 • 数 学 • 运筹学 • 组合数学 • 拉丁方 |
| 随便看 |
百科全书收录258893条中英文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。