Ричард Мэннинг Карп (родился 3 января 1935 года) — американский учёный-компьютерщик и теоретик вычислений из Калифорнийского университета в Беркли . Он наиболее известен своими исследованиями в области теории алгоритмов , за которые он получил премию Тьюринга в 1985 году, медаль Бенджамина Франклина в области компьютерных и когнитивных наук в 2004 году и премию Киото в 2008 году .
Карп был избран членом Национальной инженерной академии (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-полноты задач, что привело к идентификации многих теоретических и практических задач как вычислительно сложных.
