迈克尔·拉宾 (科学家)

迈克尔·O·拉宾（，， ）是一名以色列计算机科学家，1976年图灵奖得主。

 生平 
拉宾出生于德国布雷斯劳（二战后成为波兰弗羅茨瓦夫），父亲是一个拉比。

1953年，他获得希伯来大学的理学硕士，1956年获普林斯顿大学博士学位。

1959年，拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”（）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（）的演讲。图灵奖的引文是：

非确定自动机已经成为计算复杂度理论中的一个重要概念，特别是在描述P与NP问题的复杂度类时。

1969年，拉宾证明N successors的二阶逻辑是可判定的。证明的关键部分暗示了的确定性。1975年，拉宾发明了米勒-拉宾检验，这是一个相当快速的随机化算法（有较小的可能性错误），用于判断一个大数是否是素数。 快速素数检验是目前大部分公钥密码体系的关键。1979年，拉宾发明了第一个非对称密码系统——。它的安全性被证明和整数因式分解的复杂度相同。1981年，拉宾提出了不经意传输技术。 1987年，拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

 参考 

 外部链接 
 Short Description in an Information Science Hall of Fame at University of Pittsburgh 
 Oblivious transfer
 Quotes from some of Professor Rabin's classes 
 Website for one of Rabin's courses 

Category:以色列计算机科学家
Category:圖靈獎獲得者
Category:猶太科學家
Category:普林斯頓大學校友
Category:耶路撒冷希伯來大學校友
Category:耶路撒冷希伯来大学教师
Category:以色列猶太人
Category:20世纪德国犹太人
Category:西里西亞人