美报文章《苏联的一项发现震动数学界》

【本刊讯】美国《纽约时报》十一月七日刊登马尔科姆·布郎的一篇文章，题为《苏联的一项发现震动数学界》，摘译如下：
一个不出名的苏联数学家的一项惊人发现，震动了数学界和计算机分析界，专家们已经开始探索它的实际应用方面。
数学家们说，Ｌ·Ｇ·哈奇安的发现，是计算机能够用来有保证地解一类很难的问题的方法，对于这些难题迄今为止一直是在一种偶然碰巧的基础上解的。
这项发现除含有深刻的理论意义之外，它也许还可以应用于天气预报、复杂的工业生产过程、炼油、大工厂工人排班、密码和其它许多方面。
一位研究计算机方法的著名专家、斯坦福大学的乔治·丹特齐克博士说：“实际上政府各个部门都纷纷要求我阐明这项发现的重大意义。”
计算机解数学题必须分成一系列的步骤。有一类题的解题步骤有时异常繁重，可能需要计算数十亿年。
俄国的这项发现提供了大大减少解题步骤的一种方法。它还使数学家可以迅速判明一道题是否有解，而不必做完所要求的全部大量的演算。
据美国《科学》杂志报道，这项发现在今年一月份的苏联《学报》上首次作了报道。然而，当时它没有引起西方的注意，部分原因是因为这篇文章是俄文的，部分原因是因为文章作者在数学界是个无名之辈，他也许是个研究生。
终于，俄国这篇论文引起了加利福尼亚大学伯克利分校尤金·劳勒博士的应有的注意。自那以后几个月来，在斯坦福大学工作的两名数学家匈牙利塞格德大学的拉斯洛
·洛瓦斯和罗彻斯特大学的彼得·高奇分析了俄国这篇论文，而且在他们自己发表的论文中作了阐述。丹特齐克博士说，近几天来向大学索取这篇论文的要求象潮水般的涌来。
俄国的发现提出了一个用计算机解与“货郎担问题”（ＴＲＡＶＥＬＩＮＧＳＡＬＥＳＭＡＮＰＲＯＥＬＥＭ）有关的一类问题的方法。“货郎担问题”是数学上最有名的难题之一。
这个问题研究的是：推销员要走几个城市，在不走重复回头路的情况下如何确定一条最短路线。表面上看，这个问题似乎简单，而事实上，计算机日常的工作就是对这类问题的实际应用提供工作答案。
用现有的一些数学方法，常常有可能出一些这样没有解的问题。
在数学上，很难解的问题和无法解的问题在理论上的区分是一个重要的区分，它可能对编制密码这样的实际应用产生深远的影响。保护计算机数据若干年前，有一个计算机专家小组建议，用货郎担问题的系统进行编码来保护计算机数据的秘密。这项建议的提出，在科学界和政府中引起了一场大争论。
这项建议的基本思想是，据信对因子为素数的大数进行因子分解实际上是解不开的。素数就是只能被本身和１除尽、而不能被任何其它整数所除尽的数，如３、５、７、１１。把一个数进行因子分解就是把这个数分解成若干较小的数，它们相乘的积就是原来那个数。例如，１２的因子可能是２和６，或３和４，或２和３。
如果能够证明：计算机能够在适当的时间内破译根据把大数分解成素数因子的办法编制的密码，那末，这种编码方法大概将变得不那么安全了。这个编码理论终将受到俄国这一发现的影响，而这个事实对各国情报机构来说则有着明显的重要性。据信没有一个政府现在使用这样的密码。
哈奇安先生提出的所谓线性规划问题的解法，看来是那样简单，使好几位美国数学家为之叹服。悟出了极其重要的教训据美国著名计算机专家之一、新泽西州霍尔姆德尔贝尔实验室的罗纳德·Ｌ·格雷厄姆说：“这里面有一条重要的教训。有一些事情，不要仅仅因为你解决不了，就以为那有多难。也许一个容易的解就近在眼前，可是你却失之交臂。”
格雷厄姆说：“就我们所知，还没有人把哈奇安的思想用于实际的计算机程序中，但是已经开始积极进行实验了。”
他说，对哈奇安的思想表现出强烈兴趣的政府组织中，有全国大气研究中心。了解天气和气候机制的一些问题非常非常复杂，许多问题在当前用计算机进行计算，没有数十亿世纪的时间是算不出来的。