Ричард Мэннинг Карп (родился 3 января 1935 года) — американский учёный-компьютерщик и теоретик вычислений в Калифорнийском университете в Беркли . Он наиболее известен своими исследованиями в области теории алгоритмов , за которые он получил премию Тьюринга в 1985 году, медаль Бенджамина Франклина в области компьютерных и когнитивных наук в 2004 году и премию Киото в 2008 году . [2]
Карп был избран членом Национальной инженерной академии (1992) за большой вклад в теорию и применение NP-полноты, построение эффективных комбинаторных алгоритмов и применение вероятностных методов в информатике.
Родился в Бостоне, штат Массачусетс , у родителей Авраама и Роуз Карп , у Карпа есть трое младших братьев и сестер: Роберт, Дэвид и Кэролин. Его семья была еврейской , [3] и он вырос в маленькой квартире, в тогдашнем преимущественно еврейском районе Дорчестер в Бостоне.
Оба его родителя были выпускниками Гарварда (его мать в конечном итоге получила степень Гарварда в возрасте 57 лет после окончания вечерних курсов), в то время как его отец имел амбиции поступить в медицинскую школу после Гарварда, но стал учителем математики, так как не мог позволить себе плату за обучение. [3] Он учился в Гарвардском университете , где получил степень бакалавра в 1955 году, степень магистра в 1956 году и степень доктора философии по прикладной математике в 1959 году. Он начал работать в исследовательском центре Томаса Дж. Уотсона компании IBM .
В 1968 году он стал профессором компьютерных наук, математики и исследования операций в Калифорнийском университете в Беркли . Карп был первым ассоциированным заведующим кафедрой компьютерных наук в составе кафедры электротехники и компьютерных наук. [4] За исключением 4-летнего периода работы профессором в Вашингтонском университете , он оставался в Беркли. С 1988 по 1995 и с 1999 года по настоящее время он также был научным сотрудником в Международном институте компьютерных наук в Беркли, где в настоящее время возглавляет группу алгоритмов.
Ричард Карп был награжден Национальной медалью науки , а также был удостоен премии Харви Техниона и медали Бенджамина Франклина 2004 года в области компьютерных и когнитивных наук за свои идеи в области вычислительной сложности . В 1994 году он был введен в должность члена Ассоциации вычислительной техники . Он был избран в 2002 году в состав членов Института исследований операций и управленческих наук . [5] Он является обладателем нескольких почетных степеней и членом Национальной академии наук США , [6] Американской академии искусств и наук , [7] и Американского философского общества . [8]
В 2012 году Карп стал директором-основателем Института теории вычислений Саймонса при Калифорнийском университете в Беркли . [9]
Карп сделал много важных открытий в области компьютерных наук, комбинаторных алгоритмов и исследования операций . Его основные текущие исследовательские интересы включают биоинформатику .
В 1962 году он совместно с Майклом Хелдом разработал алгоритм Хелда–Карпа , точный экспоненциальный алгоритм для задачи коммивояжера .
В 1971 году он совместно с Джеком Эдмондсом разработал алгоритм Эдмондса–Карпа для решения задачи максимального потока в сетях, а в 1972 году опубликовал знаменательную статью по теории сложности «Сводимость среди комбинаторных задач», в которой доказал, что 21 задача является NP-полной . [10]
В 1973 году он и Джон Хопкрофт опубликовали алгоритм Хопкрофта–Карпа , самый быстрый из известных методов поиска паросочетаний максимальной мощности в двудольных графах .
В 1980 году Карп совместно с Ричардом Дж . Липтоном доказал теорему Карпа–Липтона (которая доказывает, что если задачу SAT можно решить с помощью булевых схем с полиномиальным числом логических элементов , то полиномиальная иерархия схлопывается до своего второго уровня).
В 1987 году он совместно с Майклом О. Рабином разработал алгоритм поиска строк Рабина–Карпа .
Его цитата [11] для премии Тьюринга (1985) была следующей:
За его постоянный вклад в теорию алгоритмов, включая разработку эффективных алгоритмов для сетевых потоков и других задач комбинаторной оптимизации, идентификацию вычислимости за полиномиальное время с интуитивным понятием алгоритмической эффективности , и, что наиболее примечательно, за вклад в теорию NP-полноты . Карп представил ныне стандартную методологию доказательства того, что задачи являются NP-полными, что привело к идентификации многих теоретических и практических задач как вычислительно сложных.
