Ричард Карп¶

Ричард Карп (англ. Richard Karp; род. 3 января 1935, Бостон, Массачусетс, США) — американский учёный в области теории вычислительных машин и систем, профессор Калифорнийского университета в Беркли. Лауреат премии Тьюринга (1985) за фундаментальный вклад в теорию алгоритмов, в частности за разработку теории NP-полноты и доказательство NP-полноты ряда классических задач. Член Национальной академии наук США, Американской академии искусств и наук, иностранный член Лондонского королевского общества.

¶Биография

Ричард Мэннинг Карп родился в Бостоне в семье Абрахама Карпа и Розы Карп. Окончил Гарвардский колледж в 1955 году со степенью бакалавра искусств (A.B.) по математике. В 1959 году получил степень доктора философии (Ph.D.) по прикладной математике в Гарвардском университете под руководством Энтони Отингера. Тема диссертации — «Некоторые задачи теории сетей».

С 1959 по 1968 год работал в исследовательском центре IBM имени Томаса Уотсона. В 1968 году перешёл в Калифорнийский университет в Беркли, где стал профессором компьютерных наук и математики. В 1995—1999 годах занимал должность заведующего кафедрой компьютерных наук. В 2000 году ушёл в отставку с должности профессора, но продолжает активную научную деятельность в статусе эмерита.

¶Научные достижения

¶Теория NP-полноты

Основной вклад Карпа в информатику связан с формализацией и популяризацией понятия NP-полноты. В 1971 году Стивен Кук опубликовал работу, в которой показал, что задача выполнимости булевых формул (SAT) является NP-полной. В 1972 году Карп опубликовал статью «Сводимость комбинаторных задач» (Reducibility Among Combinatorial Problems), в которой доказал NP-полноту 21 классической задачи, включая задачу о вершинном покрытии, задачу о клике, задачу о гамильтоновом цикле, задачу коммивояжёра и задачу о рюкзаке. Этот набор задач стал известен как «21 NP-полная задача Карпа» и до сих пор используется в учебниках по теории алгоритмов.

Карп ввёл понятие полиномиальной сводимости (сводимости по Карпу), которое стало стандартным инструментом для доказательства NP-полноты. Его работа заложила основу для современной теории сложности вычислений.

¶Алгоритмы и комбинаторная оптимизация

Карп внёс значительный вклад в разработку эффективных алгоритмов для задач комбинаторной оптимизации. Он разработал:

• Алгоритм Карпа — Миллера — Розенберга для поиска максимального потока в сети.
• Алгоритм Карпа — Рабина (совместно с Майклом Рабином) для поиска подстроки в строке, основанный на хешировании.
• Алгоритм Карпа — Флойда (совместно с Робертом Флойдом) для нахождения минимального остовного дерева в графе.
• Алгоритм Карпа — Хелда (совместно с Майклом Хелдом) для решения задачи коммивояжёра методом динамического программирования.

¶Теория случайных графов и вероятностные алгоритмы

Карп активно работал в области вероятностных алгоритмов и теории случайных графов. Он исследовал поведение алгоритмов на случайных входных данных, в частности, для задачи о выполнимости (SAT) и задачи о максимальной клике. В 1980-х годах он совместно с Джоном Хопкрофтом и другими учёными разработал методы анализа среднего времени работы алгоритмов.

¶Биоинформатика

В 2000-х годах Карп обратился к задачам биоинформатики. Он занимался проблемами сборки генома, выравнивания последовательностей и моделирования белковых взаимодействий. В 2002 году он совместно с коллегами предложил алгоритм для сборки генома методом «перекрытия — консенсуса», который лёг в основу многих современных программных пакетов.

¶Награды и признание

• Премия Тьюринга (1985) — «за фундаментальный вклад в теорию алгоритмов, включая разработку эффективных алгоритмов для потоков в сетях и других комбинаторных задач, а также за вклад в теорию NP-полноты».
• Национальная научная медаль США (1996) — за выдающийся вклад в компьютерные науки.
• Премия Харви (2004) — за вклад в теорию сложности вычислений.
• Премия Киото (2008) — в категории «Информатика».
• Премия Бенджамина Франклина (2011) — в области компьютерных и когнитивных наук.
• Премия Дейкстры (2012) — за работы по распределённым алгоритмам.

Карп является членом Национальной академии наук США (1980), Американской академии искусств и наук (1985), Лондонского королевского общества (2004). В 2010 году он был награждён медалью Джона фон Неймана.

¶Влияние на образование

Карп известен как автор учебников и лекционных курсов. Его книга «Комбинаторные алгоритмы» (совместно с Майклом Хелдом) долгое время использовалась в ведущих университетах мира. Он также является соавтором учебника «Алгоритмы: построение и анализ» (совместно с Томасом Корменом, Чарльзом Лейзерсоном и Рональдом Ривестом), который считается классическим пособием по алгоритмам.

¶Интересные факты

• Карп является одним из немногих учёных, получивших премию Тьюринга за работы, выполненные в промышленной лаборатории (IBM).
• В 1990-х годах он активно участвовал в разработке алгоритмов для криптографии, в частности для задачи дискретного логарифмирования.
• Карп — заядлый шахматист, в молодости участвовал в турнирах по шахматам, но не достиг профессионального уровня.
• Его имя носит гипотеза Карпа — недоказанное утверждение о том, что для любой NP-полной задачи не существует полиномиального алгоритма, если P ≠ NP.

¶Критика и дискуссии

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

¶Источники

• Karp, R. M. «Reducibility Among Combinatorial Problems». In: Miller, R. E., Thatcher, J. W. (eds.) Complexity of Computer Computations. Plenum Press, 1972.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms. 3rd ed. MIT Press, 2009.
• Garey, M. R., Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
• Национальная академия наук США. Biographical Memoirs: Richard M. Karp. 2015.
• Премия Тьюринга. Richard M. Karp — A.M. Turing Award Laureate. ACM, 1985.