NPC问题及某些近似算法

在计算机科学,运筹学,图论,电网络,数论以及其它的离散数学领域里,提出了一些很困难的问题。例如,布尔函数简化问题,排序问题,货郎问题,最小反馈问题,最小复盖问题,最长路问题以及图的色数问题等等。多年来,世界上许多科学工作者,为了得到这些问题解的有效算法,付出了巨大的努力,但收效却甚微。一直到七十年代初期,Cook和Karp提出了NP完全性理论后,对这些问题的‘攻击’才暂时告一段落,从而转向对它们的近似算法的研究。