АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ

Кук, Стивен Артур

Стивен Артур Кук (англ. Stephen Arthur Cook; род. 14 декабря 1939, Буффало, Нью-Йорк, США) — американский учёный в области теории вычислительных систем, почётный профессор Торонтского университета. Знаменит своей работой над теорией сложности вычислений, лауреат премии Тьюринга.

В своей работе «The Complexity of Theorem Proving Procedures» Кук доказал, что задача выполнимости булевых формул является NP-полной. Тем самым он поднял вопрос о равенстве классов сложности P и NP, один из сложнейших вопросов теории вычислительных систем, на который до сих пор нет ответа.

Член Канадского королевского общества (1984), Национальной академии наук США (1985)[1], Лондонского королевского общества (1998)[2].

Общие сведения
Стивен Артур Кук
Stephen Arthur Cook
Имя при рождении англ. Stephen Arthur Cook
Дата рождения 14 декабря 1939(1939-12-14) (86 лет)
Место рождения Буффало, штат Нью-Йорк, США
Страна
Научная сфера информатика
Место работы Калифорнийский университет в Беркли
Торонтский университет (почётный профессор)
Образование
Учёная степень доктор наук
Научный руководитель Ван Хао (Hao Wang)
Ученики Уолтер Савич
Известен как Теория сложности вычислений
Награды и премии Премия Тьюринга
Сайт cs.toronto.edu/~sacook/

Биография

Кук получил титул бакалавра в Мичиганском университете в 1961 году. Год спустя он получил степень магистра наук в Гарварде, где в 1966 году достиг степени доктора философии. До 1970 года работал ассистентом (англ. assistant professor) по математике в Беркли, где так и не получил статус постоянного сотрудника. Ричард Карп, лауреат премии Тьюринга 1985 года, скажет об этом

Это навсегда останется нашей виной, что мы не смогли уговорить факультет математики дать ему этот статус.

— Ричард Карп к 30-летию факультета информатики Беркли

Эту честь ему оказал Торонтский университет, назначив Стивена Кука профессором в 1975 году. В 1985 году он был удостоен высшего академического звания «университетский профессор» (англ. University Professor), а впоследствии получил статус почётного профессора (англ. University Professor Emeritus) на факультетах компьютерных наук и математики[3].

Научная деятельность

Основной вклад Стивена Кука в информатику связан с заложением основ теории NP-полноты. В 1971 году он опубликовал работу «The Complexity of Theorem Proving Procedures», в которой ввёл понятие NP-полных задач и доказал, что задача выполнимости булевых формул (SAT) является NP-полной (результат известен как теорема Кука — Левина)[4][5][6]. Эта работа формально поставила проблему равенства классов P и NP[5][3].

Значительный вклад учёный внёс в теорию сложности доказательств: в 1979 году совместно с Робертом Рекхау он формализовал понятие пропозициональной системы доказательств.

К другим областям научных интересов Кука относятся семантика языков программирования и параллельные вычисления[5][3].

Награды

  • 1982 — Премия Тьюринга «За существенный прогресс, достигнутый им в понимании сложности вычислений. Его работа положила основу теории NP-полноты. Исследование свойств и границ этого класса стало одним из важнейших направлений теории вычислительных систем за последние десять лет.»
  • 1999 — CRM-Fields-PIMS prize
  • 2012 — Канадская золотая медаль Герхарда Херцберга
  • 2013 — Орден Онтарио[7]
  • 2015 — BBVA Foundation Frontiers of Knowledge Awards «За его важную роль в определении того, что компьютеры могут и не могут эффективно решать. Его работы оказали огромное влияние на всех полях, где сложные вычисления имеют решающее значение.»
  • 2015 — офицер Ордена Канады за основополагающий вклад в теоретическую информатику и математику[7]

Избранные публикации

  • «The complexity of theorem-proving procedures» (1971)
  • «Soundness and completeness of an axiom system for program verification» (1978)
  • «The relative efficiency of propositional proof systems» (1979, соавтор Р. Рекхау)
  • «A taxonomy of problems with fast parallel algorithms» (1985)
  • «A new recursion-theoretic characterization of the polytime functions» (1992, соавтор С. Беллантони)[8]

Примечания

  1. ↑ Кук, Стивен Артур на сайте Национальной академии наук США  (англ.)
  2. ↑ Stephen Cook Архивная копия от 31 августа 2019 на Wayback Machine (англ.)
  3. ↑ 1 2 3 Some of the deepest questions it’s possible to ask: Stephen Cook’s pioneering career in computational complexity. University of Toronto News. Дата обращения: 3 мая 2026.
  4. ↑ Stephen A. Cook. Heidelberg Laureate Forum. Дата обращения: 3 мая 2026.
  5. ↑ 1 2 3 Stephen Cook. NSERC. Дата обращения: 3 мая 2026.
  6. ↑ Cook-Levin Theorem or Cook's Theorem. GeeksforGeeks. Дата обращения: 3 мая 2026.
  7. ↑ 1 2 U of T computer scientist receives international award, pushing frontiers of knowledge. University of Toronto News. Дата обращения: 3 мая 2026.
  8. ↑ Stephen A. Cook. Google Scholar. Дата обращения: 3 мая 2026.

Ссылки

Дополнительно по теме

Категории