Ричард Карп — человек, который показал, какие задачи «трудные»
Американский учёный Ричард Карп родился 3 января 1935 года. В 1972 году он доказал NP-полноту 21 классической задачи — эта работа стала основой теории сложности алгоритмов. В 1985-м Карп получил премию Тьюринга, «нобелевку» в информатике.
Ричард Мэннинг Карп родился в Бостоне. Он окончил Гарвард, где защитил диссертацию, несколько лет проработал в исследовательском центре IBM, а затем много лет преподавал в Калифорнийском университете в Беркли.
Статья 1972 года «Сводимость среди комбинаторных задач» связала теорему Кука о NP-полноте с реальной практикой: Карп показал, что десятки известных задач — о рюкзаке, о клике в графе, о раскраске, о гамильтоновом цикле — одинаково трудны. Если найти быстрый алгоритм хотя бы для одной из них, он найдётся для всех. Вопрос, возможно ли это, известный как проблема «P против NP», до сих пор не решён и входит в список задач тысячелетия.
Имя Карпа носят и практические алгоритмы: алгоритм Эдмондса — Карпа для поиска максимального потока, Хопкрофта — Карпа для паросочетаний и алгоритм Рабина — Карпа для поиска подстроки в тексте.
Фамилия Карп встречается у разных народов. У евреев-ашкеназов и немцев она связана с названием рыбы, а у восточных славян может происходить от церковного имени Карп (греч. «плод»). Её носят около 18 тысяч человек в мире.
Герой истории
род. 1935 · США
Американский учёный в области теории вычислительных систем