互动科普

克服计算困难

Joseph F. Traub ，Henryk Wozniakowski

只要满足于平均结果，则那些本来是无法解决的问题现在也能够计算了。

虽然数学家和科学家必定属于世界上最有理解力的人之列，但他们也常常承认自己深受一种灾祸之害。这一被称为“维数灾难”的现象是许多人都经历过的，只过表现形式各有不同罢了。例如，某个家庭关于是否用一项为期15年或30年的贷款来使其抵押展期的决定是极为棘手的，因为这一选择取决于多种因素的相互作用，包括每月的开支、收入、未来的赋税及利率，以及其它种种不确定因素。科学上的问题就更复杂、更难对付得多了。例如，在药物的计算机辅助设计中，可能需要确定一种候选药物与生物受体相结合的紧密程度。假定该药物、生物受体及溶剂中的原子数目通常为8000个，那

么，由于每个原子的位置需要用三个空间变量来描述，因此这项计算涉及到24000个变量。简言之，需要考虑的变量(即维数)越多，完成一项任务的难度就越大。对于许多问题，难度随变量数目的增加而呈指数增长。

维数灾难可使问题的难度增大到难于对付的程度。即使科学家们有计算机可用，一个问题的变量数也可以多到无论汁算机将来的运算速度有多大增长，也不可能在合理的时间内解出问题的地步。

难于处理的问题是否可以变成能够处理的问题(也就是用比较少的计算机时间就可以解出的问题)?幸运的是，有时候这个问题的答案是肯定的。不过我们必须乐于容忍在我们的计算中不再能保证只出现小误差。只要容忍在大多数时候(不是永远)出现小误差，则某些类型的多变量问题就可以变成能够处理的问题。本文作者之一(Wozniakowski)已从形式上证明了这方法至少对科学和工程任务中经常出现的两类数学问题有效。第一类是积分问题(积分是微积分学的基本组成部分之一)。第二类是表面重构问题，即利用各部分信息重构出一个物体(这一方法是医学成象术的基础)。

科学以外的其它领域也能从克服计算困难的各种方法中获益。例如，金融机构常常需要给一批抵押品估价，而这一估价受续贷的受抵押人的影响。如果我们假定有一批为期30年的抵押品，且允许每月续抵，则这一任务的变量数就为30(年)×12(月)，即360。这批抵押品的价值与今后30年的利率有关，而这些利率当然是未知的，这就进一步增大了问题的难度。

我们将介绍计算困难发生的原因，并讨论那些有时使我们得以克服这类困难的方法。这个问题属于“基于信息的复杂性”这一新领域，它研究的是那些无法精确求解的问题的计算复杂性。我们也将简要地探讨一下基于信息的复杂性理论如何使我们得以证明，由于宇宙中不存在必要的计算资源，某些科学问题是永远也无法回答的。如果的确如此的话，那么这一条件就为科学上可以认识的东西规定了界限。

基于信息的复杂性重点研究所谓连续问题的计算难度。行星运动的计算便是一个例子。此运动受一个常微分方程组——即描述行星位置对时间的函数关系的方程组——的支配。由于时间可取任意实数值，因此这个数学模型称为连续的。连续问题与差分方程之类的离散问题不同(在差分方程中时间只取整数值)。在研究捕食者——被捕食者群体时预测捕食者的数目以及预测潮中的污染程度之类的分析将产生出差分方程。

然而，在日常的科学和工程研究过程中，连续问题的数学表述占了统治地位。它们包括了许许多多的问题，例如常微分方程和偏微分方程、积分方程、线}生优化和非线性优化、积分和表面重构等。这些数学表述常常涉及许多变量。例如，化学、药物设计和冶金学中的计算常常需要算出成千上万个粒子的空间位置和动量。

保证得到精确数字解这一要求的固有难度常常随变量数目的增加成指数增长，最终使问题变得无法计算。这一增长速度是如此之快，以致在许多情况下，即使对于只包含中等数目的变量的情形，也不可能保证会得到适当的数字解。

为了更准确地陈述计算困难问题并讨论可能的解决办法，我们将考虑计算一条曲线下方所包围的面积这一例子。这一计算过程类似于计算书架上的一排书所占据的垂直方向上的面积。更明确地说，我们要计算的是一排书的两端上的书之间的面积。不失一般性，我们可以假设两端的书分别位于0和1处。在数学上，这一求和过程称为计算定积分。(更精确地说，这一面积是由无穷多本书占据的，每本书的厚度为无穷小。)这个问题的数学输入称为被积函数，即描述书架上的一排书的起伏变化情况的函数。

学习微积分的学生知道如何按一套预定的规则来计算定积分。这样学生们就可以得到准确的答案。但是实践中出现的绝大多数积分问题都要复杂得多，因此在学校中学到的符号方法是无法对付的。此时积分必须用数值方法近似求出，也就是用计算机来近似求解。更确切地说，需要在有限多个点上计算被积函数的值。这些被积函数值得自于所谓信息操作。然后就可以把这些值综合起来得出答案。

仅仅知道这些值并不能完全确定真正的被积函数。因为我们在有限多个点上求得被积函数的值，所以关于被积函数的信息只是部分信息。因此，积分在最好情况下也只能近似求出。通常是用指出答案的误差不超过某一误差限度的方法来规定近似解的精度。数学家用希腊字母ε来表示这一误差。

如果不加以进一步的限制，甚至这一目标也是不可能达到的。知道了被积函数在比如说0. 2和0.5这两点上的值，我们对于它在这两点之间的情况依然是一无所知。该曲线在这两点间可以取任意形状，因而可以包围任意大的一块面积。在我们所用的书架这一比喻中，这就好比是把一本精装书塞进一排平装书之中。为了确保误差不超过ε，我们必须对被积函数有一些全面的了解。例如，我们可能必须假定这函数的倾斜度始终不超过45度——或假定书架上只允许放平装书。

总而言之，试图求解积分的研究人员通常必须在计算机上用数值方法对其求解。计算机的输入是被积函数在某些点上的值。计算机产生的输出就是近似表示积分值的数字。

现在我们可以介绍计算复杂性的基本概念了。我们希望确定求解积分问题的固有难度。假定确定被积函数的值以及运用组合运算(包括加法、乘法及比较等)各有一给定成本。此成本可以就是计算机完成该项运算所需的时间。于是一积分问题的计算复杂性就可以定义为确保计算结果与真实值之差不超过误差界限e的最低成本。最优信息运算和最优组合算法就是使成本达到最小的运算和算法。

已有定理证明，这一积分问题的汁算复杂性的数量级为误差界限ε的倒数，即1／ε。换言之，可以选择一组信息运算和一种组台算法，使该问题的解可以以大致为1/ε的成本近似求出。不可能有更好的结果了。对于一个变量(即一维)的情形，问题是比较容易的。计算复杂性与所期望的精度成反比。

但是，如果这一积分问题的维数增多，计算复杂性就随着变量数的增加而呈指数式增长。如果用d表示变量的数目，则计算复杂性的数量级就为(1／ε)d，也就是误差界限的倒数的d次方。如果在计算一个有三个变量的积分时希望得到小数点后第8位的精确度(即精确到0.00000001)，则计算复舞性大致为10。换言之，为了达到这一精度水平，需要计算被积函数的1亿亿亿个值。即使我们大胆地假定存在着一台每秒可进行100亿次函数估值运算的串行计算机，这项任务也要用1百万亿秒的时间(超过3百万年)才能完成。一台有1百万个处理器的计算机仍需用1亿秒(三年左右)的时间才能完成此任务。

为了更一般地讨论多变量问题，我们必须引进另一个称为r的参数。这个参数表示数学输入的光滑度。所谓光滑，指的是数学输入中不包含有突然变化或急剧变化的函数。(数学家们的说法是，该函数直至r阶的所有偏导数为有界。)这个参数取非负整数值；该参数越大，函数就越光滑。因此，r=0就表示光滑度最低。(用专业术语来说，这时被积函数仅是连续的——它们呈相当曲折的形状，但仍连接成单一的曲线。)

许多问题的计算复杂性都大致在(1／ε)d/ε这一数量级对于专业陀更强的人来说，多变量积分、表面重构、微分方程、积分方程及非线性优化等全都具有这一计算复杂性。

如果误差界限及光滑参数不变，则计算复杂性就随维数的增加而呈指数增长。因此，在高维情况下这些问题就很难计算了。另外一个比计算困难还要严重的障碍也可能出现：一个问题可能是无法求解的。如果不能花有限的成本求出一个问题的哪怕是近似的解，则这个问题就是不可解的。数学输入是连续而曲折的问题就属于这种情形。此时光滑参数为零，而计算复杂性变为无穷大。因此，对于许多有大量变量的问题来说，确保近似解的误差在期望范围内便成了一个无法解决或很难解决的任务。

在数学上，我们所介绍的计算复杂性的结果适用于所谓最坏情形的确定性场合。“最坏情形”这个术语源自于这样一个事实，即近似求解可以保证误差始终小于ε。换言之，在多变量积分中，对于每一个有给定光滑度的被积函数，可以保证有不超过误差界限的近似解“确定性”这个术语则源自于这样一个事实，即被积函数是在确定的点而不是随机点上求值。

在这种最坏情形确定性场合中，许多多变量问题都是无法求解或很难求解的。由于这些结果是问题所固有的，因此无法通过发明其它的方法来迥避这些结果。

克服无法计算或计算困难的一条可能途径是借助于随机化。为了说明随机化方法的原理，我们将再次以多变量积分为例。此时我们不是通过确定性方法或甚至最优化方法来选取点，而是(在非正式意义上)通过抛硬币来作出决定。可以用民意测验来作一个不严格的比喻。搞民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的随机抽样调查来确定可能的优胜者。

定理表明，当随机选择一批估值时，计算复杂性至多在误差界限的平方的倒数(即1／ε2)这一数量级上。因此，即使光滑参数等于零，这个问题也永远是可以解决的。

随机化方法的关键是蒙特卡罗法。Nicholas C．Metropolis和Stanislaw M．Ulam在四十年代提出了这一设想。在经典蒙特卡罗法中，被积函数是

在均匀分布的随机点上求值的。这些函数值的算术平均就作为积分的近似解。

十分有趣的是，对于多变量积分问题，这样一种随机化使计算复杂性不再依赖于维数。根据最佳确定性点进行计算时是无法计算或计算困难的问

题，如用随机方法求解就成为能够计算的。(然而，如果r是正数，则经典蒙特卡罗法就不是最优方法，见本文的第一个框内说明。)

但是这么多结果不是凭空就能取得的。克服无法计算或计算困难所必须付出的代价就是误差至多为ε这一可靠保证不复存在了。取而代之的是一个不那么可靠的保证，也就是误差“很可能”不大于e——这就好象选举之前进行的民意测验其结果通常是正确的，但有时它预测的获胜者也不符合实际情况。换言之，最坏情况的保证是不可能实现的；人们必须满足于一项较弱的保证。

随机化使得多变量积分和其它许多重要问题的计算变得可行。但它并不是万应灵药。对于某些类型的问题，随机化完全无能为力。例如，1987年，肯塔基大学的Greg W．Wasilkowski证明了对于表面重构问题，随机化不能克服其计算困难。能够找到一种可克服表面重构的计算困难并对一大类数学问题都有用的方法吗?

事实上的确存在这种方法。这就是平均情况的场合，此时我们克服无法计算和计算困难的方法是用一个较弱的保证一期望误差至多为ε——来代替最坏情况的保证。平均情况的场合对数学输入的类型有所限制。我们选择的限制代表了最经常发生的情况。在技术上这些限制是用概率分布描述的；概率分布描述了某些输入出现的可能性。用得最多的分布是高斯测度，特别是维纳测度。

虽然从六十年代起就已经知道多变量积分平均说来是可以计算的，但它的证明却是非构造性证明。这就是说，该证明没有规定出对被积函数求值的最优点、最优组合算法以及平均计算复杂性。试图运用其它计算领域的设想来确定这些未知因素的努力没有获得成功。例如，在规则分布的点上(如网格点上)对被积函数估值是计算中常用的方法。但是有定理证明对于平均情况的场合它们不是恰当的选择。1975年，洛杉矶加利福尼亚大学的N．Donald Ylvisaker给出了一个证明。后来，在1990年，Wasilkowski和当时在哥伦比亚大学攻读博士学位的Anargyros Papageorgiou推广了这一证明。

1991年，当Wozniakowski发现了构造法时，这个问题获得了解决。象科学上有时发生的情形那样，来自数论——与平均情况复杂性理论几乎不沾边的数学分支——的一个结果发挥了关键作用。这一关键的一部分来自于伦敦帝国学院的Klaus F．Roth对数论的研究工作(Roth是1958年菲尔兹奖获得者)，另一部分则是由Wasilkowski最近的研究工作提供的。

让我们更确切地介绍一下此项结果。首先置光滑参数为零----也就是处理一个在最坏情况的确定性场合中无法解决的问题。其次假设被积函数按维纳测度分布。如果我们为了简单起见忽略某些乘数因子，则已经证明平均计算复杂性与误差界限成反比。(即在1／ε这一数量级上，见本文的第二个框内的文字。)对于误差较小的情形，这一结果比经典的蒙特卡罗法大有改进，在蒙特卡罗法中，计算成本与误差界限的平方成反比(即为1／ε2)。

平均情况提供的一类保证与随机化(蒙特卡罗)场合提供的保证不同。平均情况的场合，其误差取决于被积函数的分布，而随机化场合中，误差取决于样本点的分布。在我们用书架上的书来作的比拟中，平均情况的场合的分布可能要求排除许多尺寸过大的书，而随机化场合的分布则决定了哪些书将作为样本点。

在平均情况的场合中，最优估值点必须按确定性方式选择。最佳点是Hammersley点或双曲交叉点(见图1)。这些确定性点比随机选定的点或规则分布的点(或网格点)更好。它们使得本来不可能计算的问题平均说来成为可以解决的问题。

表面重构也是平均可解的吗?这个问题特别重要，因为正如前面已经提到的那样，随机化在此是不起什么作用的。运用我们在研究积时所用的同样一些假设，我们发现表面重构的平均计算复杂性在1／ε2这一数量级上。因此，表面重构也是平均可解的。正如积分的情形一样，双曲交叉点是最佳点。

现在我们正在检验平均情况是不是一种切实可行的替代方法。哥伦比亚大学的一位博士研究生Spassimir H．Paskov正在开发用于比较求积分的确定性方法和蒙特卡罗方法的软件。通过检验某些金融问题而获得的初步结果表明，确定性方法在实践中具有优越性。

我们的简化了的描述忽略了影响计算复杂性的一个乘数因子。这个因子与问题中的变量数有关。当变量的数目较大时，该因子可能变得非常之大。这个因子的较好的理论估计值现在还不知道，而且据认为求出这些估计值是非常困难的。

Wozniakowski发现了一个解决办法：设法去掉这个因子。具体地说，如果求解一个问题所需要的函数估值次数与变量的数目完全无关的话，我们就说这个问题是强可解的。此时需要的估值数仅取决于1／ε的某次幂。这一可能性看来是期望过高，但是去年已证明，多变量积分和表面重构二者都是平均强可解的。

还需要克服最后一个障碍才能使这些新结果得到应用。我们知道，必定存在着使积分和表面重构成为平均强可解问题的函数估值和组合算法。遗憾的是，证明这一结果并不能使我们得知具体的估值点和算法，因此给我们留下了一个有待将来解决的诱人的挑战。

对基于信息的复杂性的研究工作已使得本文作者之一(Traub)猜测，或许有可能从形式上证明某些科学问题是无法解答的。所提出的任务是要证明宇宙中不存在能够解答这类问题的计算资源(时间、存储器、能量等)。

过去60年间数学的一项重要成就是提出了关于数学问题可能是不可判定的、不能计算的或计算困难的设想。Kurt GÖdel证明了这类结果中的第一个。他证明了，在一个足够丰富的数学系统中(例如公理系统中)，存在永远不能证明的定理。

我们相信，现在是增加赌注并着手证明存在着无法解答的科学问题的时候了。换言之，我们想要证明一个物理学的GÖdel定理。这项工作提出的挑战与证明数学问题的结果是大不相同的，因为科学问题并投有配备数学表述。这类问题包括宇宙何时停止膨胀以及2001年时全球平均温度是多少等。

为什么关于计算困难的结果会表明某些科学问题可能是无法解答的呢?我们来回忆一下这些结果。在最坏情况的确定性场合中，许多连续问题的计算复杂性随维数的增加而呈指数增长。人们还猜测许多离散问题的计算复杂性也随输入数的增加而成指数增长(见本文的第三个框内的文字)。此外，虽然某些问题在随机化场合或平均情况的场合中是能够解决的，但已证明其它问题依然是难于解决的。这类问题可能存在于某些计算任务中或某些与物理学的

基础有关的问题中。无论如何，这些问题涉及大量的变量或粒子。更严重的是，许多物理问题要求解决一类称为路线积分的积分，而这种积分有无穷多维。路线积分的解导致高维近似。因此，有关计算困难的结果及猜测肯定是令人望而生畏的，因为它们表明许多有大量变量或对象的任务可能是无法解决的。

我们强调指出，科学问题的解答可能还存在其它的障碍。一个障碍是混沌，即对初始条件的极端敏感性。由于精确的初始条件不是不知道就是无法完全准确地输入数字计算机，因此关于混沌系统的行为的某些问题是不可能解答的。为了把注意力集中在现有的问题上，我们只限于讨论计算困难。

正如我们已指出的那样，科学问题并没有配备数学表述。若干个模型中的每一个都可能反映了某个科学问题的实质。由于计算困难的结果与特定的数学表述有关，因此有可能出现这样的情况，即某一数学表述虽然是难于处理的，但却可以发现另一种实际上是能够处理的数学表述。这一前景指出了一条证明存在着无法解答的科学问题的可能途径。我们可以尝试证明存在着这样一类科学问题，它的每一个反映了其实质的数学表述都是难于处理的。这样我们就将会得到科学形式的GÖdel定理。

人类不仅对未知的东西感兴趣，也对不可知的东西感兴趣。这里我们提出了一条确定科学上可能永远也无法知道的东西的可能途径。维数灾难虽然现在对许多类型的问题已被克服，但可能仍然保持着它的效力。