洪加威走向世界（上）

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

在十二届计算理论会议上，洪加威作为第一个中国代表以“三个中国人的故事”深入浅出地介绍了他出访后的第一篇成果《关于决定性空间完全性问题》。在这之前，理论界的许多学者找到了时间的完全性问题，非决定性空间的完全性问题，但一直没有找到决定性空间完全性问题。报告一结束，洪加威和他的故事立即成为会议间学者们的话题。几十位著名科学家争先前来道贺。“这真是三天会期间最好的报告。”“听你的报告真是一种享受。”不认识他的人都在问：“这个报告人是谁？你认识吗？太好了！”大会闭幕这一天，洪加威一下子接到了美国许多大学的邀请。斯坦福、麻省、康乃尔邀他去演讲。伯克利、罗彻斯特邀他去教学。卡内基一梅隆大学邀他去研究。于是，会场上纷纷传说：“三个中国人的算法”已经被10 个大学请去工作了。

但是，最让洪加威高兴的，却是会议主席米勒告诉他的话：“ACM 过去跟中国的联系太少，以后一定要特别加强。”洪加威在ACM 会议上宣读的第一篇论文，虽然赢得国际学者的普遍好评，但他真正的重大成果还在后面。在多伦多做研究时期，使他有机会了解计算理论界的最新动向和一系列重大课题。纵观这一领域几十年来的风云变幻，一个重大的突破性课题在他胸中逐渐酝酿成熟。

1980 年10 月13 日，在美国纽约州西诺求斯市，第二十一届计算机科学基础会议隆重召开。这是国际上理论计算机科学中最重要的会议之一，具有最长的历史和最高的水平。这天到会的代表，包括许多第一流的著名计算机科学家，卡尔普、罗宾，还有柯克教授，他们都带来了最重要的成果。10 月15 日，洪加威带着自信的微笑走上这庄严的国际讲台。600 多人济济一堂，聚精会神地听着这篇具有开创性的学术报告《计算的相似性与对偶性原理》。“自从图灵论题提出以来，我们知道，不同的计算模型是等价的。但我最近得出，任何合理模型所使用的并行时间、序列时间和存储空间在本质上都是一样多的，即具有所谓的相似性……”洪加威用流利的英语做了开场白。轰鸣般的掌声中洪加威结束了讲演。多少计算机科学家用敬慕的眼光看着他，他把现代计算机科学的基础——图灵论题，从本质上向前推进了一步。

“真是太漂亮了，一个惊人的报告！”著名学者鲍罗廷感慨地说道下届大会主席罗森伯向洪加威表示祝贺时说：“你的报告不仅在成果上是杰出的，在报告艺术上也是超群的。”加州大学卡尔普教授在给洪加威的一封信中写道：“听你杰出的报告是一种巨大的享受，你的研究是计算机复杂性理论中迄今所得的最杰出的成就。”（待续……）