NP问题的简单介绍

在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。
拿推销员旅行问题为例，假设推销员亨利有向6个城市推销公司产品的任务，并规定了一个旅行预算。他手中有一张航班票价表，他要从A城开始走遍图中的6个城 市后返回A城，并且不超出预算，请你帮他找出应走的路线。如果给出的预算宽裕，则任务很简单；如果预算比较紧张，你就得认真设计路线了。你得考虑每一种可 能的次序，以使旅费最少。

推销员旅行问题

如果有3个城市A，B和C，互相之间都有往返的飞机，而且起始城市是任意的，则有6种访问每个城市的次序：ABC,ACB,,BAC,BCA, CAB,CBA。如果有4个城市，则有24种次序，可以用阶乘来表示：4！=4×3！=4×3×2×1=24；若有5个城市，则有5！=5×4！= 120，类似的有6！=720等等。即使用计算机来计算，这种急剧增长的可能性的数目也远远超过计算资源的处理能力，对此，算法复杂性专家史蒂芬.库克 （Stephen Cook）评论："如果有100个城市，需要求出100！条路线的费用，没有哪一台计算机能够胜任这一任务。打个比方，让太阳系中所有的电子以它旋转的频 率来计算，就算太阳烧尽了也算不完。问题的关键是某些东西在实践中行不通。"
而NP问题中最困难的问题称之为NP完全问题，已经证明的包括：电话网络的最优几何设计、格子棋的最佳走法。根据库克定理，任意一个NP完全问题如果能够在多项式时间内解决，则所有的NP问题都能在多项式时间内解决，而至今这一问题仍无答案。