当前位置:2019年全年资料免费公开i > 确定型图灵机 >

lol的p=np什么意思

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  P是一系列问题的集合,这些问题都能够让一台确定性图灵机在多项式时间内解决。

  NP也是一系列问题的集合,这些问题能够让一台非确定性图灵机在多项式时间中解决。

  简单的说,你可以认为一台非确定性图灵机的计算能力等价于无数台确定性图灵机并行在一起。或者用一个更形象地例子,一台非确定性图灵机就像一台有着无数个CPU的计算机——这显然是不可能真正存在于世上的——那么这样的一台计算机能够在多项式时间中解决的问题,能不能被转换成一台普通计算机在多项式时间内解决的问题?

  事实上大部分研究者也是这么认为的,目前大家的看法基本上就是P !=NP。

  另外顺便说一下,某种角度上讲,目前正在不断展开各种研究的量子计算机就是对非确定性图灵机的一种模拟。因为量子计算机使用量子作为计算单元,一台量子计算机中存在的核心数量将非常大,某种程度上近乎于无穷,即在一定程度上可以模拟非确定性图灵机。

  而如果P真的被证明等于NP(虽然这怎么想怎么不可能),那么这意味着我们之前使用的算法中有一大批都是可以继续提高效率的,计算时间(至少是理论上)会被大大缩短,使用计算机的行业效率会急剧上升——会伤心的大概只有密码学,不过即使P=PN被证明为假,为了应付量子计算机他们也得研究新的算法……

http://bylaurene.com/quedingxingtulingji/437.html
点击次数:??更新时间2019-07-07??【打印此页】??【关闭
  • Copyright © 2002-2017 DEDECMS. 织梦科技 版权所有  
  • 点击这里给我发消息
在线交流 
客服咨询
【我们的专业】
【效果的保证】
【百度百科】
【因为有我】
【所以精彩】