NP完全问题是什么?

NP完全问题是什么?
NP完全问题是什么?

NP完全问题是什么?
NP完全问题,是世界七大数学难题之一.NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题.简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P.
　　数学上著名的NP问题,完整的叫法是NP完全问题,也即“NP COMPLETE”问题,简单的写法,是 NP=P?的问题.问题就在这个问号上,到底是NP等于P,还是NP不等于P.证明其中之一,便可以拿百万美元大奖.
　　多流水线调度实际上是一个NP完全问题这个奖还没有人拿到,也就是说,NP问题到底是Polynomial,还是Non-Polynomial,尚无定论.
　　NP里面的N,不是Non-Polynomial的N,是Non-Deterministic,P代表Polynomial倒是对的.NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题.
　　美国麻州的克雷(Clay)数学研究所于2000年5月24日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事：对七个“千僖年数学难题”的每一个悬赏一百万美元.以下是这七个难题.
　　“千僖难题”之一：P (多项式算法)问题对NP (非多项式算法)问题
　　“千僖难题”之二：霍奇(Hodge)猜想
　　“千僖难题”之三：庞加莱(Poincare)猜想
　　“千僖难题”之四：黎曼(Riemann)假设
　　“千僖难题”之五：杨－米尔斯(Yang-Mills)存在性和质量缺口
　　“千僖难题”之六：纳维叶－斯托克斯(Navier-Stokes)方程的存在性与光滑性
　　“千僖难题”之七：贝赫(Birch)和斯维讷通－戴尔(Swinnerton-Dyer)猜想
　　NP完全问题排在百万美元大奖的首位,足见他的显赫地位和无穷魅力.
　　NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题.
　　什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果.但是,有些问题是无法按部就班直接地计算出来.比如,找大质数的问题.有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的.再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式.
　　这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果.这也就是非确定性问题.而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的.这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间内算出来,就叫做多项式非确定性问题.而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题.
　　完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果.但是这样算法的复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了.
　　人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题.既然这类问题的所有可能答案,都可以在多项式时间内计算,人们於是就猜想,是否这类问题,存在一个确定性算法,可以在指数
　　时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想.
　　解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题.另外的一种可能,就是这样的算法是不存在的.那么就要从数学理论上证明它为什么不存在.
　　前段时间轰动世界的一个数学成果,是几个印度人提出了一个新算法,可以在多项式时间内,证明某个数是或者不是质数,而在这之前,人们认为质数的证明,是个非多项式问题.可见,有些看来好象是非多项式的问题,其实是多项式问题,只是人们一时还不知道它的多项式解而已.
　　上回说到可怜的旅行商想找出走遍所有城市的最短路径.让我们用计算机帮他搜索一下.
　　这就需要用到本篇文章中要介绍的第一门学科了：《人工智能》.人类的许多活动,如解算题、猜谜语、进行讨论、编制计划和编写计算机程序,甚至驾驶汽车和骑自行车等等,都需要"智能".如果机器能够执行这种任务,就可以认为机器已具有某种性质的"人工智能".现在我们就要利用人工智能,用计算机模拟人的思维来搜索最短路径.
　　想像一下,我们人思考问题时,有两种方法：一种是精确搜索,就是试验所有的可能性,找出最精确的一个方案.但它在搜索过程中不改变搜索策略,不利用搜索获得的中间信息,它盲目性大,效率差,用于小型问题还可以,用于大型问题根本不可能；另一种叫做启发式搜索,它在搜索过程中加入了与问题有关的启发性信息,用以指导搜索向着一个比较小的范围内进行,加速获得结果.