洪加威：数学巨匠传奇，改写计算机科学基石

1978年初，美籍华裔著名科学家王浩教授来华访问，经丁石孙介绍，王浩了解了洪加威的工作能力，回国后他把这些情况及洪加威早年在《中国科学》上发表的两篇论文介绍给国际计算机理论界的权威——多伦多大学的柯克教授。第二年10月，洪加威受柯克邀请，以客座教授的身份去多伦多和美国研究和讲学。正是这次北美之行，洪加威以他那机智幽默的性格和极出色的工作，给北美许多科学家以及整个计算理论界留下了难以忘怀的印象。

在十二届计算理论会议上，洪加威作为第一个中国代表以“三个中国人的故事”深入浅出地介绍了他出访后的第一篇成果《关于决定性空间完全性问题》。在这之前，理论界的许多学者找到了时间的完全性问题，非决定性空间的完全性问题，但一直没有找到决定性空间完全性问题。报告一结束，洪加威和他的故事立即成为会议间学者们的话题。几十位著名科学家争先前来道贺。

“这真是三天会期间最好的报告。”

“听你的报告真是一种享受。”不认识他的人都在问：“这个报告人是谁？你认识吗？太好了！”

大会闭幕这一天，洪加威一下子接到了美国许多大学的邀请。

斯坦福、麻省、康乃尔邀他去演讲。

伯克利、罗彻斯特邀他去教学。

卡内基一梅隆大学邀他去研究。

于是，会场上纷纷传说：“三个中国人的算法”已经被10个大学请去工作了。

但是，最让洪加威高兴的，却是会议主席米勒告诉他的话：“ACM过去跟中国的联系太少，以后一定要特别加强。”

洪加威在ACM会议上宣读的第一篇论文，虽然赢得国际学者的普遍好评，但他真正的重大成果还在后面。在多伦多做研究时期，使他有机会了解计算理论界的最新动向和一系列重大课题。纵观这一领域几十年来的风云变幻，一个重大的突破性课题在他胸中逐渐酝酿成熟。(www.xing528.com)

1980年10月13日，在美国纽约州西诺求斯市，第二十一届计算机科学基础会议隆重召开。这是国际上理论计算机科学中最重要的会议之一，具有最长的历史和最高的水平。这天到会的代表，包括许多第一流的著名计算机科学家，卡尔普、罗宾，还有柯克教授，他们都带来了最重要的成果。

10月15日，洪加威带着自信的微笑走上这庄严的国际讲台。600多人济济一堂，聚精会神地听着这篇具有开创性的学术报告《计算的相似性与对偶性原理》。

“自从图灵论题提出以来，我们知道，不同的计算模型是等价的。但我最近得出，任何合理模型所使用的并行时间、序列时间和存储空间在本质上都是一样多的，即具有所谓的相似性……”洪加威用流利的英语做了开场白。

轰鸣般的掌声中洪加威结束了讲演。多少计算机科学家用敬慕的眼光看着他，他把现代计算机科学的基础——图灵论题，从本质上向前推进了一步。“真是太漂亮了，一个惊人的报告！”著名学者鲍罗廷感慨地说道下届大会主席罗森伯向洪加威表示祝贺时说：“你的报告不仅在成果上是杰出的，在报告艺术上也是超群的。”加州大学卡尔普教授在给洪加威的一封信中写道：“听你杰出的报告是一种巨大的享受，你的研究是计算机复杂性理论中迄今所得的最杰出的成就。”

为了说明洪加威这篇论文究竟有什么重大意义，我们还要从图灵论题谈起。

千百年来，数学家们都确信这样一个事实，凡是正确的数学命题，就一定能找到证明的方法。然而，德国数学家哥德尔在1931年发表了一篇爆炸性的论文，它证明了有些正确的数学命题是不可以被证明的。这个结论把一个重要的数学难题摆在了人们的面前：怎样判断一类数学问题是机械可解的，或者说能通过有限的固定步骤得到解决？正当许多大数学家一筹莫展之时，英国一位24岁的数学家图灵异想天开地搬出了一种“理想计算机”，并且说，凡我这台计算机能算出的，就是可计算的，凡我这台计算机算不出的，就是不可计算的。这就是赫赫有名的“图灵机”。那么是不是一切判断能否计算问题非要在图灵机上定义，用别的计算模型就不能定义呢？接着，图灵提出了这样一个论题：只要在一个模型下可以计算，那末在别的“合理”的模型下也可以计算，你能算的我也能算，你不能算的我也无可奈何。这便是日后被称为计算机科学基石的图灵论题。

然而，图灵只考虑任何数学问题在理论上是否可计算，却没有研究实际当中能否计算的问题。换句话说，即使现代最快的计算机，也仍得考虑时间的因素。举个例子来说，写出26个英文字母的全部排列，即使一架机器每秒能写一亿个排列，也需要好几亿年才能完成。由此可见，计算问题光考虑能否计算还不行，还得讲点“效率”，这便是当今计算理论界最热门的复杂性问题。

洪加威刚刚跨入这个领域时，正值理论界群星荟萃，百家争鸣的年月。许多有名望的学者都在不同侧面、具体问题上探索着复杂性理论。他没有把精力耗费在别人的成果上做些添枝加叶的工作，而是以高屋建瓴之势，洞察到了复杂性理论关键问题的所在。他把图灵论题推进了一大步，提出了这个轰动理论界的相似性原理。这个原理指出：不但各合理模型能否计算的问题是一样的，而且计算模型所用到的三种资源：并行时间，串行时间及存储空间在本质上一样多。它表明，不仅计算的可能性是客观实在，而且计算的复杂性也是一种客观实在。

“会当凌绝顶，一览众山小”。作为一个出色的科学家，不仅需要有滴水穿石般积累起来的扎实功底，更需要具有那种能透过具体问题，观其大略、扭转乾坤的气魄。相似性原理不仅统一了所有的计算模型，而且统一了所有的计算类型。因而它已成为现代复杂性理论中的重要的基础工作之一。

加拿大多伦多大学计算机科学系主任鲍罗廷写给我国有关负责人的信中说：“洪加威的论文是质量很高的研究篇章。我认识到，这些论文对我的思路和我的同事柯克教授和拉道夫教授的思路都产生了影响……洪加威已成为对我们系做出巨大贡献的人。”