欢 迎 访 问 卢 昌 海 个 人 主 页

除了自己的无知,
我什么都不懂。

-苏格拉底

 
信 息
 
 
 
已发表作品列表
站长简介 | 常见问题
版权说明 | 电子信箱
 
统 计
 
 
 
自 2012-06-01 以来
本文点击数
39,278
自 2008-02-01 以来
本站点击数
17,221,268
昨日点击数 4,966
今日点击数 4,099
 
备 注
 
 
 

本文首发于《科学画报》 2012 年第 6 期 (上海科学技术出版社出版)。 2016 年 3 月, 本文连同本人的讨论区回帖一同应约发表于《中国数学会通讯》 2016 年 3 月刊 (中国数学会主办)。

打印版

物理学是困难的——数学家的证言?

- 卢昌海 -

本文是替《科学画报》撰写的专栏短文, 本站版本在若干人名和术语初次出现时注有英文。

2012 年 3 月, 著名物理学刊物《物理评论通讯》(Physical Review Letters) 发表了西班牙马德里大学 (Complutense University of Madrid) 的数学家丘比特 (Toby S. Cubitt) 及同事的一项有趣的研究, 其结论被许多媒体描述为: 物理学是困难的。

对多数人来说, 这也许没什么新鲜的, 因为物理学一向就被认为是困难的。 不过, 当普通人说 “物理学是困难的” 时, 如果我们追问: 什么叫做 “困难的”? 如何证明 “物理学是困难的”? 多半会被视为抬杠。 但同样的话成为数学家的证言时, 这些就不再是抬杠, 而变成非常有趣味的问题了。

那么就让我们探究一下其中的趣味吧。

先说说 “困难的”。 数学家对数学问题——确切地说是所谓的判定问题 (decision problem)——的困难度有着严格的分类, 其中最常用的两个类别是 P 和 NP, 前者是在多项式时间 (polynomial time) 内能找到答案的问题; 后者则是在多项式时间内能验证答案的问题。 这其中 “多项式时间内” 指的是用理想计算机——也叫图灵机 (Turing machine)——为工具所需花费的时间随输入信息数量的增加不快于某个多项式函数。 在这两个类别中, P 是困难度最低的, NP 则由于只对验证答案的时间作了限定, 从而有可能包含某些无法在多项式时间内找到答案——即比 P 问题更困难——的问题。 为了方便起见, 数学家们将 NP 问题中最困难的称为 NP 完全 (NP complete) 问题。 而 “困难的” 这一概念, 它的全称乃是 “NP 困难的” (NP hard), 指的是起码跟 NP 完全问题一样困难 (但不一定属于 NP 这一类别)。 限于篇幅, 对 “最困难” 及 “一样困难” 这两个概念我们只得割爱了, 但请相信我, 它们也是有严格定义的, 并非偷梁换柱。

接下来说说如何证明 “物理学是困难的”。 丘比特等人认为, 很大一部分物理学所研究的乃是物理体系的状态演化, 其形式类似于数学上的马尔科夫过程 (Markov process), 特点是每个时刻的状态都可以通过一个所谓的转移矩阵, 从前一时刻的状态中计算出来。 利用这种类似性, 研究物理体系的状态演化可以抽象为一个数学问题, 即通过实验数据确定转移矩阵。 而这一数学问题——丘比特等人证明了——是跟一个已被证明为是 “困难的” 的数学问题一样困难的。 这样, 他们就证明了 “物理学是困难的”——当然, 如前所述, 这是媒体对他们结论的描述, 丘比特等人原始论文的措辞要严密得多。

由于是第一次有人对 “物理学是困难的” 这一含义模糊的老生常谈给出精确描述及证明, 丘比特等人的研究引起了很多人的兴趣, 其中既有对结论的兴趣, 也有对日常概念精确化的好奇。 有些媒体则很替物理学家们高兴, 因为 “物理学是困难的” 意味着物理学家们不必担心计算机能抢他们的饭碗。

不过, 将丘比特等人的研究结论描述为 “物理学是困难的” 其实是有一定误导性的。

首先, 从物理上讲, 稍有研究经验的人都知道, 物理学家们研究物理体系的状态演化根本就不会采用通过实验数据确定转移矩阵那样笨拙的、 本质上是将有规律现象视为随机现象来处理的数学方法。 丘比特等人通过该方法得出的结论究竟有多大意义, 是值得商榷的。 其次, 哪怕从数学上讲, 把 “NP 困难的” 说成 “困难的” 起码在目前也还缺乏依据。 细心的读者也许注意到了, 我们在提到 NP 有可能包含某些比 P 问题更困难的问题时, 用了 “有可能” 一词。 之所以要用这个词, 是因为数学家们尚未排除 NP 与 P 这两个类别完全相同的可能性。 事实上, 这两个类别是否相同乃是理论计算机科学中最著名的未解之谜, 也是美国克雷数学研究所 (Clay Mathematics Institute) 列出的 “千禧年问题” (Millennium Problems) 之一。 假如 NP 与 P 这两个类别完全相同, 那么 NP 完全问题就并不比困难度最低的 P 问题更困难, NP 困难的问题也未必比困难度最低的 P 问题更困难。 因此, 无论从物理还是数学上讲, 将丘比特等人的研究结论描述为 “物理学是困难的” 都是有一定误导性的。

不过, 媒体有一点也许说对了, 那就是物理学家们不必担心计算机能抢他们的饭碗。 只不过原因恐怕并非是丘比特等人的研究, 而是因为物理学很微妙, 绝非丘比特等人所设想的数学问题所能代表。

站长往年同日 (6 月 1 日) 发表的作品

站长近期发表的作品

网友讨论选录

  • 网友: 来自 85.180 的游客   (发表于 2012-06-01)

    我觉得无论是 P 还是 NP, 计算 1023 个粒子都是不现实的。

  • 网友: lifubo   (发表于 2012-06-01)

    我觉得论文中的假设不一定成立。 比如, 人不是图灵机。 图灵本人很早就已经说到过这一点了。 人可能犯错, 不按照程序规定动作而出的错误恰恰有可能导致新的发现。 另外, 本文的论点, 研究 NP 问题的人其实都知道, 算是一个 folk theorem, 数年之前我就听人说过, 不过不是说的物理, 而是数学, 即数学或者一般的科学研究都至少是 NP 难问题。 只不过人们都不拿这个当回事。 另外即使科学研究是 NP 难的, 也不能由此证明计算机不可能抢去科学家的饭碗。 我认为不可能这么容易就能证明机器不能超过人力。 其实 von Neumann 认为我们甚至不能证明计算机不能完成某项人可以完成的智力任务。 象棋、 国际象棋, 都是至少 NP 难的, 但是现在人下不过机器了。 我想这一点对于该文的论点是致命的。 NP 难和通常的难不是同一个意思。

  • 网友: 卢昌海   (发表于 2012-06-01)

    good point! 需要稍稍解释的是: “物理学是困难的” 以及 “物理学家们不必担心计算机能抢他们的饭碗” 并不是丘比特等人论文中的说法, 而是媒体的引申。 我对那种引申的评述侧重于联系论文本身的内容, 但那种引申从很多其它角度——比如 fubo 兄所提的角度——上讲也是不恰当的。

    来自 85.180 的游客说得也很对, 无论 P 还是 NP, 也无论它们的难度对比从理论上讲如何, 实际上用丘比特等人所说的确定转移矩阵那样的 “死算” 方法来对付 1023 个粒子都是不现实的。 在我个人看来——如我在文末所说, 计算机是否能抢物理学家们的饭碗, 关键并不在于 P 和 NP, 而在于物理学是微妙的, 其中充满了无法用规则死板的棋类游戏或丘比特等人所设想的数学问题来模拟的技巧。

本文的讨论期限已过, 如果您仍想讨论本文,
请在每个月前七天的 “读者周” 期间前来讨论。

>> 查阅目前尚在讨论期限内的文章 <<