Карп, Ричард Мэннинг

Ричард Карп родился в 1935 году в семье учителя математики и директора средней школы Эйбрахама Луиса Карпа (1908—1981) и его жены Розы (Роуз) Карп (1912—2000), из семей еврейских иммигрантов из России, в Бостоне, штат Массачусетс. С ним росли двое младших братьев Роберт и Дэвид (род. 1944, социолог) и младшая сестра Кэролин.

Окончив школу, Ричард поступил в Гарвардский университет, где получил степени бакалавра (1955), магистра наук (1956) и наконец доктора философии по прикладной математике в 1959 году.

После учёбы Ричард Карп работал 9 лет в исследовательском центре IBM (Исследовательский центр Томаса Вотсона). В 1968 году он получил профессуру по информатике, математике и исследованию операций в Калифорнийском университете в Беркли, где работает по сей день, не считая перерыва на работу в Вашингтонском университете в Сиэтле с 1995 по 1999 год. В 2012 году Карп стал директором-основателем Института Саймонса по теории вычислений при Калифорнийском университете в Беркли и руководил им до 2017 года. Он также является научным сотрудником в Международном институте компьютерных наук (ICSI).

В 1971 году Карп вместе с Джеком Эдмондсом разработал алгоритм для нахождения максимального потока в транспортной сети, названный в их честь. Год спустя, Карп опубликовал свой труд «Reducibility Among Combinatorial Problems», в котором он доказал NP-полноту для 21 задачи.

В 1973 году Карп и Джон Хопкрофт опубликовали алгоритм Хопкрофта — Карпа, который является самым быстрым известным методом для нахождения максимальных соответствий количества элементов в двудольных графах.

В 1980 году, вместе с Ричардом Дж. Липтоном, Карп доказал теорему Карпа — Липтона.

В 1987 году, вместе с Майклом Рабином, Карп разработал алгоритм поиска подстроки, названный в их честь. Алгоритм Рабина — Карпа находит широкое применение в современной геномике и биоинформатике для задач анализа последовательностей ДНК^[7].

Ричард Карп сделал много других важных открытий в информатике и исследовании операций в области комбинаторных алгоритмов. Среди других высокоцитируемых работ Карпа — соавторство в создании модели параллельных вычислений LogP (1993) и архитектуры одноранговых сетей CAN (2001)^[8]. На сегодняшний день он занимается исследованиями в биоинформатике. В 2025 году Карп в соавторстве с Иланом Адлером и Шелдоном М. Россом опубликовал статью «Improved bounds on the probability of a union and on the number of events that occur» в журнале Operations Research Letters^[9].

• В конце февраля 2009 года Карп занимал 35 место в списке самых цитируемых авторов в проекте CiteSeer.
• 1977 — Премия Фредерика Ланчестера, ORSA
• 1979 — Премия Фалкерсона, Американское математическое общество
• 1985 — Премия Тьюринга «за его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты.»
• 1987 — Лекция Джона фон Неймана
• 1990 — Теоретическая премия фон Неймана, ORSA
• 1994 — почётное членство ACM
• 1995 — Премия имени Чарльза Беббиджа
• 1996 — Национальная научная медаль США
• 1998 — Премия Харви, Израильский технологический институт
• 2004 — Медаль Бенджамина Франклина
• 2008 — Премия Киото
• 2008 — Премия Диксона
• 2019 — Институт Саймонса учредил серию «Выдающихся лекций Ричарда М. Карпа» (Richard M. Karp Distinguished Lectures) в честь его вклада в теоретическую информатику.