简介

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

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

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

“ 因他们的合著论文“有限自动机与其判定性问题”。论文中引入了非确定自动机的概念，被证明是（计算理论科学研究中的）一个非常重要的概念。拉宾和斯科特的这篇经典论文成为了这个领域后续研究的源泉。 ”

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

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

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。