Стивен Кук

Стивен Кук (англ. Stephen Cook; род. 14 декабря 1939, Буффало, штат Нью-Йорк, США) — американский и канадский учёный в области теории вычислительных систем и математики, профессор компьютерных наук Торонтского университета. Наиболее известен как один из основоположников теории NP-полноты и автор формулировки проблемы «P vs NP», которая является одной из семи «задач тысячелетия» (Millennium Problems), за решение которых Математическим институтом Клэя объявлен приз в 1 миллион долларов США. Лауреат премии Тьюринга (1982).

Биография

Стивен Артур Кук родился в Буффало, штат Нью-Йорк. Его отец, Фредерик Кук, был химиком, а мать, Мэри Кук, — домохозяйкой. Интерес к математике и логике проявился у Кука ещё в школьные годы.

Кук получил степень бакалавра наук (B.Sc.) по физике в Мичиганском университете в 1961 году. Затем он поступил в Гарвардский университет, где в 1962 году получил степень магистра (M.Sc.) по математике, а в 1966 году — докторскую степень (Ph.D.) по математике. Его диссертация, выполненная под руководством Хао Вана, была посвящена теории рекурсии и сложности алгоритмов.

После получения докторской степени Кук работал в Калифорнийском университете в Беркли (1966–1970). В 1970 году он перешёл на факультет компьютерных наук Торонтского университета (Канада), где проработал до выхода на пенсию. В 1985 году он был назначен профессором университета (University Professor) — высшее академическое звание в Торонтском университете.

Научный вклад

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

Главным достижением Кука является формулировка и доказательство теоремы Кука — Левина (1971). В своей основополагающей статье «Сложность процедур вывода теорем» (The Complexity of Theorem-Proving Procedures) он ввёл понятие NP-полноты.

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

Проблема «P vs NP»

Кук также сформулировал центральную проблему теории сложности вычислений: «Совпадают ли классы P и NP?» (P vs NP). Класс P состоит из задач, которые могут быть решены за полиномиальное время на детерминированной машине Тьюринга. Класс NP — из задач, чьё решение может быть проверено за полиномиальное время. Вопрос о том, равен ли P NP, остаётся открытым с 1971 года. Большинство специалистов полагают, что P ≠ NP, однако строгого доказательства не существует. Проблема включена в список «задач тысячелетия» Математического института Клэя.

Другие направления

Кук внёс вклад и в другие области теории вычислительных систем:

• Теория сложности доказательств: Кук изучал, как сложно доказать математические утверждения в формальных системах. Он разработал концепцию полиномиально ограниченных доказательств.
• Теория параллельных вычислений: Совместно с учениками Кук исследовал сложность задач при параллельных вычислениях, ввёл класс NC (Nick's class) — задачи, решаемые за полилогарифмическое время на полиномиальном числе процессоров.
• Квантовые вычисления: В последние годы Кук занимался вопросами сложности квантовых алгоритмов и их отношением к классическим классам сложности.

Признание и награды

• Премия Тьюринга (1982) — высшая награда в области информатики, присуждена Ассоциацией вычислительной техники (ACM) за «вклад в теорию сложности вычислений, в частности за формулировку NP-полноты».
• Премия Кнута (1999) — за выдающийся вклад в теоретическую информатику.
• Премия CRM-Fields-PIMS (2006) — совместная награда канадских математических институтов.
• Премия Шовене (2008) — за выдающуюся статью по истории математики.
• Член Королевского общества (1998) — Лондонского.
• Член Королевского общества Канады (1983).
• Иностранный член Национальной академии наук США (2003).

Влияние на науку

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

Кук также воспитал многих учеников, ставших ведущими учёными в области теории сложности, среди которых — Тони Хоар, Пол Бисон, Роберт Ирвинг.

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

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

Основные публикации

• Cook, S. A. (1971). «The complexity of theorem-proving procedures». Proceedings of the Third Annual ACM Symposium on Theory of Computing: 151–158.
• Cook, S. A. (1973). «A hierarchy for nondeterministic time complexity». Journal of Computer and System Sciences 7 (4): 343–353.
• Cook, S. A. (1983). «The complexity of the comparison of two strings». Journal of Algorithms 4 (1): 1–15.
• Cook, S. A. (1994). «A short proof of the PCP theorem». Proceedings of the 35th Annual Symposium on Foundations of Computer Science: 2–11.

Источники

• Stephen Cook — A biography. University of Toronto, Department of Computer Science.
• The Complexity of Theorem-Proving Procedures (1971) — оригинальная статья.
• ACM Turing Award citation for Stephen Cook (1982).
• Математический институт Клэя. Описание проблемы «P vs NP».
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2005). Алгоритмы: построение и анализ (2-е изд.). — Глава 34: NP-полнота.
• Ахо, А., Хопкрофт, Дж., Ульман, Дж. (1979). Структуры данных и алгоритмы. — Раздел о NP-полноте.