|||
Alan Cobham(1927-2011)是最早提出“多项式时间复杂度问题类P”的学者之一,他1965年的文章“The Intrinsic Computational Difficulty of Functions(函数计算的内在难度)”被认为是计算复杂性理论的重要论文之一,被Cook在其1971年的著名论文“The complexity of theorem proving procedures”中引用。
Alan Cobham的工作直接产生“Cobham–Edmonds论题”:只有在多项式时间内可计算的问题,也就是说,在复杂度P类中问题才能由计算机能行计算(“Polynomial Time”术语探源——介绍“Cobham论题)。
虽然Jack R. Edmonds(1934 -)获得1985年约翰·冯·诺依曼理论奖,但Alan Cobham 一生却从未获得过任何奖项,几乎默默无闻,。。。
Alan Cobham于1927年出生在美国的旧金山,他的父亲是丝绸商人,母亲是艺术家。
在1940年到1945年之间,Alan Cobham的家人搬到了Bronx,在那里他就读于Fieldston School,后来就读于Oberlin College。
再后来,Alan Cobham转学到芝加哥大学。1950年代初期,他在美国海军作战评估小组工作了一段时间。 尽管他从未获得博士学位,但他继续在伯克利和麻省理工学院做研究生工作。 从1960年代初期到1984年,他还曾在IBM Yorktown Heights工作。他在IBM取得的成就之一是计算机程序“ Playbridge”,这在当时是世界上玩桥牌的最佳程序之一,1984年10月7日在《纽约时报》上对此进行了介绍。 1984年秋天,艾伦(Alan)离开IBM,到康涅狄格州的Middletown,出任刚起步的Wesleyan University计算机科学系主任,任期至1988年6月30日。
Alan Cobham于2011年6月28日在康涅狄格州的Middletown逝世。
据说,他从未结过婚,也没有孩子,。。。
参考资料:
【1】Cobham–Edmonds论题(https://en.wikipedia.org/wiki/Cobham%27s_thesis)
【2】Alan Cobham: An Appreciation (http://recursed.blogspot.com/2014/11/alan-cobham-appreciation.html)
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-7-28 00:38
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社