您当前所在的位置:主页 > 美剧影评 >

细心的观众注意到查理说扫雷是一个NP问题

  在这集中发生了一系列的抢劫银行犯罪事件,但并没有出现任何暴力行为。查理推理出下一起抢劫案发生的地点之后,FBI设下了埋伏。不料被暗中隐藏的枪手大开杀戒。枪林弹雨中,一位特工中枪倒地。FBI的干预改变了抢劫犯们的行为,并且揭开了一段更加扑朔迷离的剧情……

  海森堡测不准原理真正想要表述的应该是,我们不能同时完美地测量出任何东西的精确位置与精确速度,尤其是当被测量物为一粒电子时。这个误差的结果跟普朗克常量差不多,即10-34 焦耳每秒。焦耳每秒是一个描述宏观量的单位(宏观量,比如千克和米) 所以说在宏观的体系中,这点误差小到完全可以忽略。我们测量的东西越小,这个法则就越重要。

  这个原理,从它的根基上而言,跟物理完全没有任何关系。事实上,它的基本形式解释了一个函数和它的傅里叶变换形式的关系。我们得出结论,傅里叶变换是量子力学的基础,所以傅里叶变换自然在物理学中也是有意义的。美国数学协会有一篇很精彩的文章[1],这篇文章正是从这个角度,解释了傅里叶变换。

  P/NP问题是一个逻辑学的问题(或计算机理论科学)。假设我们有一个问题,希望用计算机来解决。比如说,我们想要用计算机找出旅行商问题的答案。假设一位商人需要走过全世界的五十个城市。 已知的条件是每个城市的航班的价格,而商人想要花在路上的钱尽可能少。显然我们可以找出仅仅 50×49×48×....3×2×1 种可能的方案。没有人会想要手算每一条线路的总价格,所以我们编程,让计算机来帮我们解决这个问题。但计算机会花多少时间来解决这个问题呢? 这个问题从以下的方式被构想出来:假设我们在这个问题中有 n 个地点。有没有一个算法仅仅需要O(f(n)) 步呢?在这里,我们把大写的 O 定义为算法的渐进时间复杂度。其中 n 是问题的规模,在一个指定的数学模型中,规模往往可以由人为设定并输出此规模的结果。在代码中,n 可以理解为 input 的一个值。因此 n 可以看做是一个未知数。f(n) 可以简单理解为代码循环了 n 次。那么 O 的含义就好理解了,O 其实是一个关于f(n)的函数,有固定的推导算法,其定义了算法所需的时间与 n 的增长的关系,称为算法的渐进时间复杂度,简称时间复杂度。一般来说,如果有一个算法能够使问题在O(f(n))步以内解决,那么我们称这个问题属于 f 级别复杂度类别。

  P级别复杂度类别问题,是一个由一系列 YES/NO 问题组成的问题,并且这个问题能够在多项式时间内被解决。也就是说,P 级别复杂性类问题是说,这个问题存在着一个算法使得 O(f(n)) 小于多项式 f(n)。我们也说 P 是一些能够由多项式时间以内的算法来找出答案的问题。NP复杂性类是一些更复杂的问题。那NP和P问题有什么区别呢?有些问题计算起来很容易,利用多项式算法很快能解决,比如求若干个数的乘积,这类问题被称作 P 问题;另一类问题计算过程比较繁琐,但验证答案却很容易,比如把整数 44427 进行因数分解,求解过程可能会很费时,但如果告诉你答案是177×251,简单计算即可验证答案是对的,这类问题就被归为NP问题。也就是说如果一个验证问题答案的算法可以在多项式时间以内完成,那么是不是存在一个相应的算法,对于此问题,能够在多项式时间内找到答案? 这乍一听好像有点蠢,寻找答案与验证答案对于计算机来说几乎是同一件事,但是这是目前世界上公开的数学问题中,最棘手的一个。 P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一,只要给出正确或否定的论文并成功论证P与NP是否能够相互转化,$1,000,000的赏金就是你的囊中之物。

  细心的观众注意到查理说扫雷是一个NP问题。查理的描述其实不那么清晰,因为他没怎么讲清楚如何解决 P vs NP 问题。 NPC 问题是 NP 问题的一个小小的子集,NPC 问题有可能不是 P 问题。本质上来说,NPC问题是最难的NP问题。理查德·凯伊用数学人工智能证明了扫雷游戏是一个NPC问题。人们可以通过访问他的网站[2]获得更多有关扫雷的数学问题的信息。旅行商问题也是NPC问题。

  查理对唐说,从统计学角度上看,他已经死了。唐枪口逃生,捡回了一条命,查理认为,这种好运不会再有第二次了。查理这么说可能是正确的,一个人在枪口脱险后,他会比普通人更加容易丧命于枪口之下。 毕竟,那些经历过枪战的人更有可能参与到下一场枪战中,因为这帮人包括警察,军人,雇佣军和帮派等。查理的推断正确吗?特别地,他的哥哥是否更有可能是因为在参加的枪战中负的伤而死亡的呢?(完)

上一篇:经典美剧《 越狱》第5季开播 下一篇:“倍速” 能够改变播放的速率

在线客服

  • 点击这里给我发消息
  • 二维码

    微信扫一扫