Стивен Артур Кук OC OOnt (родился 14 декабря 1939 года) — американо-канадский компьютерный учёный и математик, внёсший значительный вклад в области теории сложности и сложности доказательства . Он является почётным профессором университета Торонто , кафедры компьютерных наук и кафедры математики .
Его считают одним из основоположников теории сложности вычислений .
.jpg/1280px-Stephen_A._Cook_1968_(enlarged_portion).jpg)
Кук получил степень бакалавра в 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-полных задач стало одним из самых активных и важных исследовательских направлений в области компьютерной науки за последнее десятилетие.
В своей статье «Feasibly Constructive Proofs and the Propositional Calculus» [7] , опубликованной в 1975 году, он ввел эквациональную теорию PV (сокращение от Polynomial-time Verifiable) для формализации понятия доказательств, использующих только концепции полиномиального времени. Он внес еще один важный вклад в эту область в своей статье 1979 года, написанной совместно со своим студентом Робертом А. Рекхов, «The Relative Efficiency of Propositional Proof Systems» [8] , в которой они формализовали понятия p-симуляции и эффективной системы пропозициональных доказательств , что положило начало области, которая теперь называется сложностью пропозициональных доказательств . Они доказали, что существование системы доказательств, в которой каждая истинная формула имеет короткое доказательство, эквивалентно NP = coNP . Кук был соавтором книги со своим студентом Фуонгом Те Нгуеном в этой области под названием «Logical Foundations of Proof Complexity». [9]
Его основные области исследований — теория сложности и сложность доказательства , с экскурсами в семантику языков программирования , параллельные вычисления и искусственный интеллект . Другие области, в которые он внес вклад, включают ограниченную арифметику , ограниченную обратную математику , сложность функций высшего типа, сложность анализа и нижние границы в системах пропозициональных доказательств .
Он назвал класс сложности NC в честь Ника Пиппенгера . Класс сложности SC назван в его честь. [10] Определение класса сложности AC 0 и его иерархии AC также введены им. [11]
По словам Дона Кнута, алгоритм KMP был вдохновлен автоматами Кука для распознавания конкатенированных палиндромов за линейное время . [12]
Кук был награжден стипендией NSERC EWR Steacie Memorial Fellowship в 1977 году, исследовательской стипендией Killam в 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]
