NP完全问题

NP完全问题 数理化力学卷 NP完全问题
　　简称“NPC问题”。具有如下共性的一类NP问题:(1)类中每一个问题都还未找到多项式算法;(2)若类中有一个问题是P问题,则类中所有问题都是P问题。NP完全问题由库克(S.A.Cook)于1971年给出,至今已有近千个问题属于此类,包括哈密顿圈问题、0-1背包问题等许多著名问题,人们越来越相信NPC问题不是P问题。2000年5月法国克莱(Clay)数学研究所悬赏解决七个千禧年数学难题,其中第一个问题就是NPC=P?
出处：数理化力学卷-->数　　学-->运筹学·组合数学-->拉丁方