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

P对NP的世界

Polynomial时间和指数时间的比赛

 
 
 

日志

 
 

南水北调工程的是否是NP判定问题  

2009-12-20 17:22:18|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
根据TM机(图灵机)的定义,我们可以提出一个基本判定问题
            南水北调工程是否是一个灾难工程

根据图灵定义:现在这个问题属于不可判定问题(NP问题),因为我们无法验证该问题是否正确或者错误。所以,存在不是NP问题的问题。

但更大问题是,假设这个工程实施了K年后,那么它的影响和后果,并不需要k^n 才能看出来,可能只要k+1,或者k+2年就知道了。因为,辣手问题出现,我们不能等那天才作判定。所以,NP问题可能是不完备的。

  评论这张
 
阅读(252)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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