Введение

Американские математики:

Фейт Эллен
Салли Флойд
Филипп Гиббонс
Дэн Гасфилд
Нарендра Кармаркар
Валери Кинг
Майкл Люби
Раджив Мотвани
Ноам Нисан
Раймонд Райтер
Юнис Сантос
Томас Дж. Шефер
Рон Шамир
Барбара Саймонс
Эрик Синг
Норман Заде

Карп был избран членом Национальной инженерной академии (1992) за значительный вклад в теорию и применение NP-полноты, разработку эффективных комбинаторных алгоритмов и применение вероятностных методов в информатике.

Биография

Ричард Карп родился в Бостоне, штат Массачусетс, в семье Абрахама и Роуз Карп. У него три младших брата и сестра: Роберт, Дэвид и Кэролин. Его семья была еврейской, и он вырос в небольшой квартире в районе Дорчестер в Бостоне, который в то время был преимущественно еврейским. Оба родителя были выпускниками Гарварда (мать в итоге получила степень Гарварда в 57 лет, посещая вечерние курсы), а отец, хотя и мечтал поступить в медицинскую школу после Гарварда, стал учителем математики из-за нехватки средств для оплаты обучения. За исключением четырехлетнего периода работы профессором в Университете Вашингтона, он оставался в Беркли. С 1988 по 1995 год и с 1999 года по настоящее время он также является научным сотрудником Международного института компьютерных наук в Беркли, где в настоящее время возглавляет группу алгоритмов. Ричард Карп был удостоен Национальной медали науки, премии Харви Техниона и медали Бенджамина Франклина 2004 года в области компьютерных и когнитивных наук за его вклад в понимание вычислительной сложности. В 1994 году он был принят в члены Ассоциации вычислительной техники. В 2002 году он был избран членом Института операционных исследований и управленческих наук. Он является обладателем нескольких почетных степеней и членом Национальной академии наук США, Американской академии искусств и наук и Американского философского общества. В 2012 году Карп стал директором-основателем Института Симонса по теории вычислений при Калифорнийском университете в Беркли.

Работа

Карп сделал множество важных открытий в области компьютерных наук, комбинаторных алгоритмов и исследования операций. Его основные текущие исследовательские интересы включают биоинформатику. В 1962 году он совместно с Майклом Хелдом разработал алгоритм Хелда — Карпа, точный алгоритм с экспоненциальным временем работы для задачи коммивояжера. В 1971 году он совместно с Джеком Эдмондсом разработал алгоритм Эдмондса — Карпа для решения задачи о максимальном потоке в сетях, а в 1972 году опубликовал основополагающую работу в теории сложности "Сократимость комбинаторных задач", в которой доказал, что 21 задача является NP-полной. В 1973 году он и Джон Хопкрофт опубликовали алгоритм Хопкрофта — Карпа, самый быстрый известный метод поиска максимальных по размеру паросочетаний в двудольных графах. В 1980 году вместе с Ричардом Дж. Липтоном Карп доказал теорему Карпа — Липтона (которая доказывает, что если SAT может быть решена булевыми схемами с полиномиальным числом логических элементов, то полиномиальная иерархия схлопывается до второго уровня). В 1987 году он совместно с Майклом О. Рабином разработал алгоритм поиска подстроки Рабина — Карпа.