物理学是困难的——数学家的证言? - 卢昌海 - 本文是替《科学画报》撰写的专栏短文, 本站版本在若干人名和术语初次出现时注有英文。 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 日) 发表的作品 站长近期发表的作品
本文的讨论期限已过, 如果您仍想讨论本文, >> 查阅目前尚在讨论期限内的文章 << |
|
来自: 物理网文 > 《卢昌海2015.3》