曼纽尔·布卢姆——计算机复杂性理论奠基人

    ManuelBlum是卡耐基梅隆大学的计算机科学教授，并且是计算复杂性理论的主要创始人之一。他是密码学和程序验证领域的先驱，在理论计算机科学领域享有盛誉。1995年，他认识到他对计算复杂性的理论基础的贡献以及对计算复杂性理论在密码学中的应用的贡献。
    曼纽尔·布卢姆出生在委内瑞拉的加拉加斯，他的父母在20世纪30年代逃离欧洲后定居在那里。20世纪50年代中期他来到美国，在麻省理工学院学习。在学习电气工程的同时，布卢姆还在沃伦·S·麦卡洛奇和沃尔特·皮特的神经生理学实验室工作，来追求理解思维和大脑工作原理的愿望。他说过，“我与神童相反”——他在小时候就想知道大脑是如何工作的，原因是他想变得更聪明。后来，他专注于数学逻辑和递归理论，以获得对大脑和思维的洞察力。他在人工智能先驱马文·明斯基的指导下，于1964年获得了麻省理工学院数学博士学位。
    布卢姆在麻省理工学院开始了他的数学教学生涯，1968年，他加入了加州大学伯克利分校。2001年，他接受了卡内基梅隆大学的现职。布卢姆和他培养的博士生，在理论计算机科学领域做出了许多突破性贡献，被认为是一个传奇。
    布卢姆除了在计算复杂性理论方面作出了开创性贡献以外，还致力于将这一理论应用于对计算机系统的安全性和通信的安全性有十分重要意义的“密码学”以及在“软件工程”中十分重要而又十分困难的程序正确性验证方面，并且取得了令人瞩目的成就。1989年5月，他和同事SampathKannan在西雅图召开的21届ACM计算理论专题研讨会上所提交的一篇论文中，首次提出了ProChecker的概念，并综合利用密码学、概率算法和程序测试、概率交互证明等手段解决程序正确性验证这一难题，把这一领域的研究推进了一大步。有兴趣的读者可参阅他们发表在J．ACM1995年1月号上的论文DesigningProgramsthatCheckTheirWork。大家知道，Intel公司在推出其著名的奔腾微处理器Pentium。以后不久，被人发现该处理器的除法运算存在一个细微问题，从而引起了一场轩然大波。布卢姆和他的学生瓦塞曼（H．Wasserman）仔细地研究和分析了这个问题，提出了解决方案和应吸取的教训。他们的有关论文ReflectionsonthePentiumDivisionBug刊载于IEEETrans.onComputer，1996年4月。在软件可靠性方面，布卢姆1997年发表的“具有运行期结果校验的软件的可靠性”一文也很值得重视。