Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3471646
  • 博文数量: 1450
  • 博客积分: 11163
  • 博客等级: 上将
  • 技术积分: 11101
  • 用 户 组: 普通用户
  • 注册时间: 2005-07-25 14:40
文章分类

全部博文(1450)

文章存档

2017年(5)

2014年(2)

2013年(3)

2012年(35)

2011年(39)

2010年(88)

2009年(395)

2008年(382)

2007年(241)

2006年(246)

2005年(14)

分类: C/C++

2006-04-29 12:07:45

也谈NP问题

方舟の女


楼下那位Mr.X扯淡么!连什么叫做NP问题都没有搞清楚,
就胡乱科普,误人子弟,本女本不想插嘴,只是这网上
这么多人,竟然没有人出来纠正他这个常识性的错误。

NP并不是NON-POLYNOMIAL,把NP说成是NON-POLYNOMIAL,
是望文生义,读书不求甚解。事实上,如果你能够证明某个
NP问题是个NON-POLYNOMIAL的问题,你就可以去领那七个
百万美元数学大奖中间的一个了。

数学上著名的NP问题,完整的叫法是NP完全问题,也即
“NP COMPLETE”问题,简单的写法,是 NP=P?的问题。
问题就在这个问号上,到底是NP等於P,还是NP不等於P。
证明其中之一,便可以拿百万美元大奖。

这个奖还没有人拿到,也就是说,NP问题到底是Polynomial,
还是Non-Polynomial,尚无定论。Mr. X信口开河敢说NP就是
Non-Polynomial,真是不知天高地厚,惹人笑话。

NP里面的N,不是Non-Polynomial的N,是Non-Deterministic,
P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial
的问题,也即是多项式复杂程度的非确定性问题。

什么是非确定性问题呢?有些计算问题是确定性的,比如
加减乘除之类,你只要按照公式推导,按部就班一步步来,
就可以得到结果。但是,有些问题是无法按部就班直接地
计算出来。比如,找大质数的问题。有没有一个公式,你
一套公式,就可以一步步推算出来,下一个质数应该是多少
呢?这样的公式是没有的。再比如,大的合数分解质因数
的问题,有没有一个公式,把合数代进去,就直接可以算
出,它的因子各自是多少?也没有这样的公式。

这种问题的答案,是无法直接计算得到的,只能通过间接
的“猜算”来得到结果。这也就是非确定性问题。而这些
问题的通常有个算法,它不能直接告诉你答案是什么,但
可以告诉你,某个可能的结果是正确的答案还是错误的。
这个可以告诉你“猜算”的答案正确与否的算法,假如可以
在多项式时间内算出来,就叫做多项式非确定性问题。而
如果这个问题的所有可能答案,都是可以在多项式时间内
进行正确与否的验算的话,就叫完全多项式非确定问题。

完全多项式非确定性问题可以用穷举法得到答案,一个个
检验下去,最终便能得到结果。但是这样算法的复杂程度,
是指数关系,因此计算的时间随问题的复杂程度成指数的
增长,很快便变得不可计算了。

人们发现,所有的完全多项式非确定性问题,都可以转换
为一类叫做满足性问题的逻辑运算问题。既然这类问题的
所有可能答案,都可以在多项式时间内计算,人们於是就
猜想,是否这类问题,存在一个确定性算法,可以在指数
时间内,直接算出或是搜寻出正确的答案呢?这就是著名
的NP=P?的猜想。

解决这个猜想,无非两种可能,一种是找到一个这样的算法,
只要针对某个特定NP完全问题找到一个算法,所有这类问题
都可以迎刃而解了,因为他们可以转化为同一个问题。另外
的一种可能,就是这样的算法是不存在的。那么就要从数学
理论上证明它为什么不存在。

前段时间轰动世界的一个数学成果,是几个印度人提出了一个
新算法,可以在多项式时间内,证明某个数是或者不是质数,
而在这之前,人们认为质数的证明,是个非多项式问题。
可见,有些看来好象是非多项式的问题,其实是多项式问题,
只是人们一时还不知道它的多项式解而已。
阅读(870) | 评论(0) | 转发(0) |
0

上一篇:NP问题的简单介绍

下一篇:也谈NP问题

给主人留下些什么吧!~~