注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

P对NP的世界

Polynomial时间和指数时间的比赛

 
 
 

日志

 
 

P=NP与世界可知论  

2010-08-26 11:42:40|  分类: 图论中NP问题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 印度学者Vinay Deolalikar 声明P=/=NP后,有人问我,继续研究P=NP的证明是否还有意义。其实可以从哲学角度甚至宗教角度出发证明P=\=NP是错误的,或者说P=NP是成立的。

唯物主义认为:世界是可知的,

佛教也认为: 世界是可知的.

P问题: 可以被确定性图灵机多项式时间内求解的问题。通俗点就是可以多项式时间内求解的判定问题(yes or no的问题): 例如,判断一堆苹果中是否有一个青色的苹果。

NP问题: 可以被非确定性图灵机多项式时间内求解的问题。 通俗点就是可以多项式时间内验证的判定问题(yes or no的问题),但未必能多项式时间给出判定的问题。 例如:判断漓江里面是否有个金耳环是NP问题,但如果找到个漓江中的耳环,判定是否是金或者银的则是P问题。

 

那么P=NP与否,假定P=/=NP,  Vinay Deolalikar等人证明是对的(还有很多证明 P=/=NP的学者),那么判定宇宙某个东西是否可知,答案是NO,因此,世界不可知。  这和唯物论的世界可知,佛教的世界可知都是矛盾的。所以P=NP成立。

 

备注:  基督教我不熟悉,不过猜想上帝是万能的,那么世界当然是可以被上帝知道的,呵呵。

  评论这张
 
阅读(925)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017