在计算复杂性理论研究中 洪加威取得突出成就 两次在国际学术会议上提出新理论受到国内外高度评价 [复制链接]

第4版()
专栏：

在计算复杂性理论研究中
洪加威取得突出成就
两次在国际学术会议上提出新理论受到国内外高度评价
本报讯 记者刘林春报道：1980年10月在美国纽约州西诺求斯召开的第二十一届IEEE计算机科学基础理论会议上，我国44岁的洪加威做的《论计算的相似性与对偶性》的学术报告，已被作为最好的论文之一选入这届会议的专集。
洪加威原是北京市计算中心副研究员。由于他在计算复杂性理论的研究中取得突出成绩，最近被提升为研究员。
洪加威在《论计算的相似性与对偶性》的论文中，提出了计算模型间的相似性和计算时间与存储空间之间的对称性这两个重要概念，证明了三条关于相似性的定理和一系列关于对偶性的定理，进而提出了相似性原理和对偶性原理。在这两个原理成立的前提下，将有可能对所有的计算模型、所有的计算类型以及复杂性分类中的几乎所有的定理做出统一的处理，并将得到一系列全新的结果。
计算复杂性理论是理论计算机科学中的一个新分支。直到不久以前，在这一领域中从事研究工作的人一般都是在证明一个个孤立的定理，解决一个个孤立的问题。洪加威的研究结果则是对这些问题进行统一的处理。国内从事计算机科学研究工作的专家认为，他的成就是很突出的。
完全性问题是理论计算机科学的又一个重要问题。多年来，学者找到了时间的和非决定性空间的完全性问题，可是一直找不到决定性的空间完全性问题。1980年4月洪加威在美国洛杉矶召开的第十二届ACM计算机理论会议上，第一次提出了决定性空间完全性问题。这也是计算复杂性理论中的一项重要成果。
1979年洪加威经北京大学数学系丁石孙教授介绍，通过华裔数学家王浩教授举荐，由加拿大多伦多大学柯克教授邀请，担任该校计算机科学系客座教授。他先后两次在国际学术会议上提出的新理论，引起了许多国家计算机科学家的重视，并受到高度评价。美国加州大学贝克利分校著名计算机科学家卡尔普写给他的信中说：“听你杰出的报告是一种莫大的享受。你的研究可列入在计算复杂性理论方面迄今所得到的最杰出的工作之中。”加拿大多伦多大学计算机科学系主任鲍罗廷写给我国有关负责人的信中说：洪加威的论文“是质量很高的研究篇章。我认识到这些论文对我的思路和我的同事柯克教授和拉道夫教授的思路都产生了影响……洪加威已成为对我们系做出巨大贡献的人。”