Майкл Озер Рабин ( иврит : מִיכָאֵל עוזר רַבִּין ; родился 1 сентября 1931 года) — израильский математик , ученый-компьютерщик , лауреат премии Тьюринга .
Рабин родился в 1931 году в Бреслау , Германия (сегодня Вроцлав , Польша ), в семье раввина . В 1935 году он эмигрировал с семьей в подмандатную Палестину . В детстве он очень интересовался математикой, и отец отправил его в лучшую среднюю школу в Хайфе , где он учился у математика Элиши Нетаньяху , который тогда был учителем средней школы. [1]
Рабин окончил еврейскую школу Reali в Хайфе в 1948 году и был призван в армию во время арабо-израильской войны 1948 года . Математик Авраам Френкель , который был профессором математики в Иерусалиме , вмешался в ситуацию с армейским командованием, и Рабин был демобилизован для обучения в университете в 1949 году. [1] После этого он получил степень магистра наук в Еврейском университете в Иерусалиме . Он начал аспирантуру в Университете Пенсильвании, прежде чем получить степень доктора философии в Принстонском университете в 1956 году. [2]
Рабин стал доцентом математики в Калифорнийском университете в Беркли (1961–62) и Массачусетском технологическом институте (1962–63). До перехода в Гарвардский университет в качестве профессора компьютерных наук имени Гордона Маккея в 1981 году он был профессором в Еврейском университете. [3]
В конце 1950-х годов его пригласили на лето для проведения исследований для IBM в поместье Лэмб в округе Вестчестер, штат Нью-Йорк, вместе с другими перспективными математиками и учеными. Именно там он и Дана Скотт написали статью «Конечные автоматы и проблемы их принятия решений». [4] Вскоре, используя недетерминированные автоматы, они смогли передоказать результат Клини о том, что конечные автоматы точно принимают регулярные языки. [1]
Что касается истоков того, что должно было стать теорией вычислительной сложности , то следующим летом Рабин вернулся в поместье Лэмба. Джон Маккарти задал ему загадку о шпионах, охранниках и паролях, которую Рабин изучил и вскоре после этого написал статью «Степень сложности вычисления функции и иерархия рекурсивных множеств». [1] [5]
Недетерминированные машины стали ключевой концепцией в теории сложности вычислений, особенно с описанием классов сложности P и NP .
Затем Рабин вернулся в Иерусалим, исследуя логику и работая над основами того, что позже стало известно как компьютерная наука . В 29 лет он стал доцентом и главой Института математики в Еврейском университете, а к 33 годам стал полным профессором. Рабин вспоминает: «Работа по проблемам вычислений не получила абсолютно никакой оценки. Математики не признавали зарождающуюся новую область». [1]
В 1960 году Эдвард Ф. Мур пригласил его работать в Bell Labs , где Рабин представил вероятностные автоматы , которые используют подбрасывание монеты, чтобы решить, какие переходы состояний предпринять. Он показал примеры регулярных языков, которые требовали очень большого количества состояний, но для которых вы получаете экспоненциальное сокращение количества состояний с вероятностными автоматами. [1]
В 1966 году (опубликовано в трудах конференции 1967 года) [6] Рабин ввел понятие полиномиального времени (введенное независимо и незадолго до этого Кобхэмом [7] и Эдмондсом [8] ).
В 1969 году Рабин ввел автоматы с бесконечным деревом и доказал, что монадическая теория второго порядка n последователей ( S2S при n = 2) разрешима . [9] Ключевой компонент доказательства неявно показал определенность игр на четность , которые лежат на третьем уровне иерархии Бореля .
В 1975 году Рабин закончил свой срок полномочий ректора Еврейского университета в Иерусалиме и отправился в Массачусетский технологический институт в США в качестве приглашенного профессора. Находясь там, Рабин изобрёл тест Миллера–Рабина на простоту , рандомизированный алгоритм, который может очень быстро (но с небольшой вероятностью ошибки) определить, является ли число простым . [10] [11] Метод Рабина был основан на предыдущей работе Гэри Миллера , который решил проблему детерминированным образом, предполагая, что обобщенная гипотеза Римана верна, но версия теста Рабина не делала такого предположения. Быстрое тестирование на простоту является ключом к успешной реализации большинства криптографий с открытым ключом, и в 2003 году Миллер, Рабин, Роберт М. Соловей и Фолькер Штрассен получили премию Парижа Канеллакиса за свою работу по тестированию на простоту.
В 1976 году Джозеф Трауб пригласил его на встречу в Университете Карнеги-Меллона , где он представил тест на простоту, который Трауб назвал «революционным». [1]
В 1979 году Рабин изобрел криптосистему Рабина , первую асимметричную криптосистему, безопасность которой была эквивалентна сложности факторизации целых чисел . [12]
В 1981 году Рабин заново изобрел слабый вариант техники забывчивой передачи, изобретенной Визнером, под названием мультиплексирование [13], позволяющее отправителю передавать сообщение получателю, при этом получатель имеет некоторую вероятность от 0 до 1 узнать сообщение, при этом отправитель не знает, смог ли получатель сделать это.
В 1987 году Рабин совместно с Ричардом Карпом создал один из самых известных эффективных алгоритмов поиска строк — алгоритм поиска строк Рабина–Карпа , известный своим скользящим хешем . [14]
Последние исследования Рабина были сосредоточены на компьютерной безопасности. В настоящее время он является профессором компьютерных наук имени Томаса Дж. Уотсона-старшего в Гарвардском университете и профессором компьютерных наук в Еврейском университете . В течение весеннего семестра 2007 года он был приглашенным профессором в Колумбийском университете, где преподавал Введение в криптографию .
Рабин является иностранным членом Национальной академии наук США , [15] членом Американского философского общества , [16] членом Американской академии искусств и наук , [17] членом Французской академии наук и иностранным членом Королевского общества .
В 1976 году премия Тьюринга была присуждена совместно Рабину и Дэне Скотт за статью, написанную в 1959 году, в ссылке на которую указано, что награда была присуждена:
За их совместную работу «Конечные автоматы и их проблемы принятия решений», в которой была представлена идея недетерминированных машин, которая оказалась чрезвычайно ценной концепцией. Их (Скотта и Рабина) [ sic ] классическая работа стала постоянным источником вдохновения для последующих работ в этой области. [18]
В 1995 году Рабин был удостоен Премии Израиля в области компьютерных наук. [19] В 2010 году Рабин был удостоен Премии Дэна Дэвида Тель-Авивского университета (категория «Будущее») совместно с Леонардом Клейнроком и Гордоном Э. Муром за компьютеры и телекоммуникации. [20] В 2017 году Рабин был удостоен звания почетного доктора наук Гарвардского университета. [21]
У Рабина есть дочь, компьютерный специалист Таль Рабин . [22]
{{cite journal}}: CS1 maint: неподходящий URL ( ссылка )