Стивен Кук
Стивен Кук | |
|---|---|
 Кук в 2008 году | |
| Рожденный | Стивен Артур Кук 14 декабря 1939 г. Буффало , Нью-Йорк |
| Альма-матер | Гарвардский университет Мичиганский университет |
| Известный | NP-полнота предложений Сложность доказательства Теорема Кука – Левина |
| Награды |
|
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Университет Торонто Калифорнийский университет, Беркли |
| Диссертация | О минимальном времени вычисления функций (1966) |
| Докторантура | Хао Ван |
| Докторанты | Марк Браверман [1] Тонян Питасси Уолтер Савич Арвинд Гупта Анна Любив |
Стивен Артур Кук OC OOnt (родился 14 декабря 1939 г.) — американо-канадский ученый-компьютерщик и математик, внесший значительный вклад в области теории сложности и сложности доказательств . Он является почетным профессором Университета Торонто , факультет компьютерных наук и факультет математики .
Его считают одним из родоначальников теории сложности вычислений .
Биография
[ редактировать ]
Кук получил степень бакалавра в 1961 году в Мичиганском университете , а степень магистра и доктора философии в Гарвардском университете соответственно в 1962 и 1966 годах на математическом факультете. [2] Он поступил на математический факультет Калифорнийского университета в Беркли в 1966 году в качестве доцента и оставался там до 1970 года, когда ему было отказано в повторном назначении. В речи, посвященной 30-летию факультета электротехники и компьютерных наук Беркли, лауреат премии Тьюринга профессор Беркли Ричард Карп сказал: «К нашему вечному стыду, мы не смогли убедить математический факультет дать ему должность. " [3] Кук поступил на факультет компьютерных наук и математики Университета Торонто в 1970 году в качестве доцента, где он получил звание профессора в 1975 году и заслуженного профессора в 1985 году.
Исследовать
[ редактировать ]Во время работы над докторской диссертацией Кук работал над сложностью функций, в основном над умножением. В своей плодотворной статье 1971 года «Сложность процедур доказательства теорем» [4] Кук формализовал понятия сокращения за полиномиальное время (также известного как сокращение Кука ) и NP-полноты и доказал существование NP-полной проблемы, показав, что булева проблема выполнимости (обычно известная как SAT) является NP-полной . Эта теорема была независимо доказана Леонидом Левиным в Советском Союзе и поэтому получила название теоремы Кука – Левина . В статье также сформулирована самая известная проблема в информатике — проблема P и NP . Неформально вопрос «P против NP» спрашивает, может ли каждая задача оптимизации, ответы на правильность/оптимальность которой можно эффективно проверить, быть оптимально решена с помощью эффективного алгоритма. Учитывая обилие таких задач оптимизации в повседневной жизни, положительный ответ на вопрос «P против NP», вероятно, будет иметь глубокие практические и философские последствия.
Кук предполагает, что существуют задачи оптимизации (с легко проверяемыми решениями), которые не могут быть решены эффективными алгоритмами, т. е. P не равно NP. Эта гипотеза породила большое количество исследований в области теории сложности вычислений , которые значительно улучшили наше понимание внутренней сложности вычислительных задач и того, что можно вычислить эффективно. Тем не менее, эта гипотеза остается открытой и входит в число семи знаменитых задач Премии тысячелетия . [5] [6]
В 1982 году Кук получил премию Тьюринга за вклад в теорию сложности. Его цитата гласит:
За его существенное и глубокое продвижение в нашем понимании сложности вычислений. Его основополагающая статья « Сложность процедур доказательства теорем», представленная на симпозиуме ACM SIGACT 1971 года по теории вычислений, заложила основы теории NP-полноты. Последовавшее за этим исследование границ и природы NP-полного класса задач стало одним из наиболее активных и важных исследовательских мероприятий в области информатики за последнее десятилетие.
В его «Возможно конструктивных доказательствах и исчислении высказываний». [7] В статье, опубликованной в 1975 году, он представил эквациональную теорию PV (что означает «проверяемость за полиномиальное время»), чтобы формализовать понятие доказательств, используя только концепции полиномиального времени. Он внес еще один важный вклад в эту область в своей статье 1979 года, совместно со своим учеником Робертом А. Рекхоу , «Относительная эффективность систем пропозициональных доказательств». [8] в котором они формализовали понятия p-симуляции и эффективной системы пропозиционального доказательства , что положило начало области, которая теперь называется сложностью пропозиционального доказательства . Они доказали, что существование системы доказательств, в которой каждая истинная формула имеет краткое доказательство, эквивалентно NP = coNP . стал соавтором книги Кук вместе со своим учеником Фуонгом Нгуеном в этой области под названием «Логические основы сложности доказательств». [9]
Его основными областями исследований являются теория сложности и сложность доказательства , а также экскурсы в семантику языков программирования , параллельные вычисления и искусственный интеллект . Другие области, в которые он внес свой вклад, включают ограниченную арифметику , ограниченную обратную математику , сложность функций высшего типа , сложность анализа и нижние границы в системах доказательства высказываний .
Некоторые другие вклады
[ редактировать ]Он назвал класс сложности NC в честь Ника Пиппенджера . класс сложности SC . Его именем назван [10] Определение класса сложности АС 0 и его иерархия AC также введены им. [11]
По словам Дона Кнута, алгоритм KMP был вдохновлен автоматами Кука для распознавания составных палиндромов за линейное время . [12]
Награды и почести
[ редактировать ]Кук был награжден Мемориальной стипендией Стейси NSERC EWR в 1977 году, исследовательской стипендией Киллама в 1982 году и получил премию CRM-Fields-PIMS в 1999 году. Он получил премию Джона Л. Синджа и медаль Бернарда Больцано Чешской академии наук ( 2008), [13] и является членом Лондонского королевского общества и Королевского общества Канады . Кук был избран членом Национальной академии наук (США) и Американской академии искусств и наук . Он является членом-корреспондентом Геттингенской академии наук и гуманитарных наук .
ACM Кук получил премию Тьюринга в 1982 году. Ассоциация вычислительной техники удостоила его звания члена ACM в 2008 году за его фундаментальный вклад в теорию сложности вычислений . [14] Он был выбран Ассоциацией символической логики для чтения лекции Гёделя в 1999 году. [15]
В 2013 году правительство Онтарио наградило его Орденом Онтарио , высшей наградой Онтарио . [16] В 2012 году он выиграл золотую медаль Канады Герхарда Герцберга в области науки и техники , высшую награду для ученых и инженеров в Канаде. [17] Медаль Герцберга присуждается NSERC «за устойчивое превосходство и общее влияние исследовательской работы, проводимой в Канаде в области естественных наук или техники». [18] он был удостоен звания кавалера Ордена Канады . В 2015 году [19]
Кук был удостоен премии BBVA Foundation Frontiers of Knowledge Award 2015 в категории «Информационные и коммуникационные технологии» «за его важную роль в определении того, что компьютеры могут и не могут эффективно решать», по словам жюри. Его работа, продолжает он, «оказала огромное влияние во всех областях, где сложные вычисления имеют решающее значение».
Кук руководил многочисленными студентами магистратуры, а 36 аспирантов получили степени под его руководством. [1]
Личная жизнь
[ редактировать ]Кук живет со своей женой в Торонто . У них двое сыновей, один из которых — олимпийский моряк Гордон Кук . [20]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Стивен Кук в проекте «Математическая генеалогия»
- ^ Капрон, Брюс. «Стивен Артур Кук» . Премия А. М. Тьюринга . Проверено 23 октября 2018 г.
- ^ Ричард Карп (2003). «Личный взгляд на информатику в Беркли» . Калифорнийский университет в Беркли . Проверено 12 февраля 2023 г.
- ^ Стивен Кук (1971), Сложность процедур доказательства теорем (PDF) - через Университет Торонто Стивен А. Кук (2009) [1971]. «Сложность процедур доказательства теорем» . Проверено 12 февраля 2023 г.
- ^ P против NP. Архивировано 14 октября 2013 г., в задаче Wayback Machine на странице задач премии тысячелетия - Институт математики Клэя.
- ^ P против NP. Архивировано 27 сентября 2007 г., в официальном описании проблемы Wayback Machine Стивеном Куком о задачах премии тысячелетия.
- ^ Кук, Стивен А. (5 мая 1975 г.). «Практически конструктивные доказательства и исчисление высказываний (предварительная версия)» . Материалы седьмого ежегодного симпозиума ACM по теории вычислений - STOC '75 . Нью-Йорк: Ассоциация вычислительной техники. стр. 83–97. дои : 10.1145/800116.803756 . ISBN 978-1-4503-7419-4 . S2CID 13309619 .
- ^ Кук, Стивен А.; Рекхау, Роберт А. (1979). «Относительная эффективность систем доказательства высказываний». Журнал символической логики . 44 (1): 36–50. дои : 10.2307/2273702 . ISSN 0022-4812 . JSTOR 2273702 . S2CID 2187041 .
- ^ "Логические основы сложности доказательств" Официальная страница
- ^ « Класс Стива»: происхождение СК» . Теоретическая информатика — Stack Exchange .
- ^ «Кто ввел класс сложности АС?» . Теоретическая информатика — Stack Exchange .
- ^ «Двадцать вопросов Дональду Кнуту» .
- ^ «Награжден Почетной медалью Бернара Больцано за заслуги в области математических наук» . Медали CAS . Чешская академия наук . Проверено 13 апреля 2024 г.
- ^ Ассоциация вычислительной техники. «Стивен Повар» . Награды.acm.org . Проверено 12 февраля 2023 г.
- ^ «Лекторы Гёделя - Ассоциация символической логики» . Проверено 8 ноября 2021 г.
- ^ «25 назначенцев удостоены высшей награды Онтарио» . Министерство гражданства и иммиграции .
- ^ Эмили, Чанг (27 февраля 2013 г.). «Ученый-компьютерщик получил высшую научную премию Канады» . cbc.ca. Проверено 27 февраля 2013 г.
- ^ «Текущий победитель – 2012 – Стивен Кук» . 28 июня 2016 г.
- ^ «СолтВайр | Галифакс» . www.saltwire.com . Проверено 12 февраля 2023 г.
- ^ «Стивен А. Кук – Домашняя страница» .
Внешние ссылки
[ редактировать ]
- Домашняя страница Стивена А. Кука
- «P против NP» и пределы вычислений - публичная лекция Стивена Кука в Университете Торонто.
- Устное историческое интервью со Стивеном Куком в Институте Чарльза Бэббиджа , Университет Миннесоты. Кук рассказал о своем образовании в Мичиганском и Гарвардском университетах, о ранней работе в Калифорнийском университете в Беркли, а также о своем растущем интересе к проблемам вычислительной сложности. Кук рассказал о своем переезде в Университет Торонто в 1970 году и о том, как была принята его работа по NP-полноте, приведшая к получению премии А. М. Тьюринга.
- Стивен Артур Кук в проекте «Математическая генеалогия»
- Стивен А. Кук на DBLP библиографическом сервере
- Живые люди
- 1939 рождений
- Члены Национальной академии наук США
- Члены Ордена Онтарио
- Американские ученые-компьютерщики
- Канадские ученые-компьютерщики
- Лауреаты премии Тьюринга
- Члены Королевского общества
- Члены Королевского общества Канады
- Члены Ассоциации вычислительной техники 2008 г.
- Академический состав Университета Торонто
- Выпускники Мичиганского университета
- Выпускники Гарвардской высшей школы искусств и наук
- Калифорнийский университет, факультет литературы и науки Беркли
- Американские эмигранты в Канаде
- Офицеры Ордена Канады
- Теоретики-компьютерщики