普林斯顿数学指南基础知识（看经典美剧探索数学世界）

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

查理告诉唐，海森堡测不准原理认为在一个系统中，测量数据的行为会影响系统本身的数据。但查理过后也承认了，这不是原理本身描述的性质。

事实上查理的叙述并不那么严谨：假设有一粒漂浮在空气中的尘埃，而我们想要非常精确地测量出它的位置。此时我们一定会使得空气发生流动，从而使这粒尘埃分子移动。这是物理学家们习以为常的事实了。

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

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

[1] ams.org/publicoutreach/feature-column/fcarc-uncertainty

什么是 P vs NP 问题？

图自网络

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问题。

[2] web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

统计家眼中的死亡

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

参考：pi.math.cornell.edu/~numb3rs/luthy/num104.html

译者 校对：毛线团君

,