Стивен Кук - Stephen Cook

Стивен Кук
Prof.Cook.jpg
Готовим в 2008 году
Родился
Стивен Артур Кук

( 1939-12-14 )14 декабря 1939 г. (81 год)
Альма-матер Гарвардский университет
Мичиганского университета
Известен NP-полнота
Утвержденная сложность доказательства теоремы
Кука – Левина
Награды Премия Тьюринга (1982) Премия
CRM-Fields-PIMS (1999)
Премия Джона Л. Синджа (2006)
Медаль Бернарда Больцано
Герхард Герцберг, Канада, Золотая медаль в области науки и техники (2012)
Кавалер Ордена Канады (2015)
BBVA Foundation Frontiers of Knowledge Премия (2015)
Научная карьера
Поля Информатика
Учреждения Университет Торонто
Калифорнийский университет, Беркли
Тезис О минимальном времени вычисления функций  (1966 г.)
Докторант Хао Ван
Докторанты Марк Браверман
Тониан Питасси
Уолтер Савич
Арвинд Гупта
Анна Любив

Стивен Артур Кук , О.К. , Онтарио (родился 14 декабря 1939 г.), американо-канадский ученый - компьютерщик и математик , внесший большой вклад в теорию сложности и сложность доказательств . Он является профессором университета в Университете Торонто , факультет компьютерных наук и факультета математики .

биография

Повар в 1968 году

Кук получил степень бакалавра в 1961 году в Мичиганском университете , а также степень магистра и доктора философии. из Гарвардского университета , соответственно, в 1962 и 1966 годах, на факультете математики. Он поступил на математический факультет Калифорнийского университета в Беркли в 1966 году в качестве доцента и оставался там до 1970 года, когда ему было отказано в повторном назначении. В речи, посвященной 30-летию кафедры электротехники и компьютерных наук в Беркли, лауреат премии Тьюринга и профессор Беркли Ричард Карп сказал: «К нашему вечному стыду мы не смогли убедить математический факультет дать ему должность. " Кук присоединился к факультету компьютерных наук и математики Университета Торонто в 1970 году в качестве адъюнкт-профессора, где он был повышен до профессора в 1975 году и заслуженного профессора в 1985 году.

Исследовать

Стивен Кук считается одним из основоположников теории сложности вычислений .

Во время своей докторской диссертации Кук работал над сложностью функций, в основном над умножением. В своей основополагающей статье 1971 года «Сложность процедур доказательства теорем» Кук формализовал понятия редукции за полиномиальное время (также известной как редукция Кука ) и NP-полноты и доказал существование NP-полной проблемы, показав, что логическое Проблема выполнимости (обычно известная как SAT) является NP-полной . Эта теорема была независимо доказана Леонидом Левиным в Советском Союзе и поэтому получила название теоремы Кука – Левина . В статье также сформулирована самая известная проблема в информатике - проблема P vs. NP . Неформально вопрос «P vs. NP» спрашивает, можно ли оптимально решить любую задачу оптимизации, ответы на которую можно эффективно проверить на правильность / оптимальность с помощью эффективного алгоритма. Учитывая изобилие таких проблем оптимизации в повседневной жизни, положительный ответ на вопрос «P vs. NP», вероятно, имел бы глубокие практические и философские последствия.

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

В 1982 году Кук получил премию Тьюринга за свой вклад в теорию сложности. Его цитата гласит:

За его значительный и глубокий прогресс в понимании сложности вычислений. Его основополагающая статья «Сложность процедур доказательства теорем», представленная на симпозиуме ACM SIGACT по теории вычислений 1971 года, заложила основы теории NP-полноты. Последовавшее за этим исследование границ и природы NP-полного класса задач было одним из самых активных и важных исследований в области компьютерных наук за последнее десятилетие.

В своей статье «Возможные конструктивные доказательства и исчисление высказываний», опубликованной в 1975 году, он представил эквациональную теорию PV (обозначающую проверяемость с полиномиальным временем), чтобы формализовать понятие доказательств, используя только концепции полиномиального времени. Он сделал еще один важный вклад в эту область в своей статье 1979 года, совместно со своим учеником Робертом А. Рекхоу , «Относительная эффективность систем пропозициональных доказательств», в которой они формализовали понятия p-моделирования и эффективной системы пропозициональных доказательств , которые положили начало область, которая теперь называется сложностью пропозиционального доказательства . Они доказали, что существование системы доказательств, в которой каждая истинная формула имеет краткое доказательство, эквивалентно NP = coNP . Кук в соавторстве со своим учеником Фуонг Нгуеном написал книгу в этой области под названием «Логические основы сложности доказательства».

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

Некоторые другие вклады

Он назвал класс сложности NC в честь Ника Пиппенгера . Его именем назван класс сложности SC . Он также вводит определение класса сложности AC 0 и его иерархию AC .

По словам Дона Кнута KMP алгоритм был вдохновлен автоматами Кука для распознавания каскадных кодов палиндромов в линейное время .

Награды и отличия

Кук был награжден стипендией NSERC EWR Steacie Memorial в 1977 году, стипендией Killam Research в 1982 году и получил премию CRM-Fields-PIMS в 1999 году. Он получил премию Джона Л. Синджа и медаль Бернарда Больцано , а также является членом Лондонское королевское общество и Королевское общество Канады . Кук был избран членом Национальной академии наук ( США ) и Американской академии искусств и наук .

Кук получил премию ACM Turing в 1982 году. Ассоциация вычислительной техники удостоила его звания научного сотрудника ACM в 2008 году за его фундаментальный вклад в теорию вычислительной сложности .

Правительство Онтарио назначил его в Орден Онтарио в 2013 году, самая высокая честь , в Онтарио . Он выиграл Золотую медаль Герхарда Херцберга Канады в области науки и техники в 2012 году , высшую награду для ученых и инженеров Канады . Медаль Герцберга присуждается NSERC «как за устойчивое совершенство, так и за общее влияние исследовательской работы, проводимой в Канаде в области естественных наук или инженерии». В 2015 году он был удостоен звания кавалера Ордена Канады .

По словам жюри, Кук был удостоен премии BBVA Foundation Frontiers of Knowledge Award 2015 в категории «Информационные и коммуникационные технологии» «за его важную роль в определении того, что компьютеры могут и не могут решать эффективно». Его работа, продолжает он, «оказала огромное влияние на все области, где решающее значение имеют сложные вычисления».

Кук руководил многочисленными студентами магистратуры, и 34 аспиранта получили степень под его руководством.

Личная жизнь

Кук живет с женой в Торонто . У них двое сыновей, Гордон и Джеймс . Он играет на скрипке и любит плавать . Его часто называют коротким именем Стив Кук.

Профессор Стивен А. Кук (справа) со своим другом профессором Яном Крайичеком (слева) в Осенней школе логики и сложности в Праге , 24 сентября 2008 г.

Смотрите также

использованная литература

внешние ссылки