Стивен Артур Кук 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-полного класса задач было одним из наиболее активных и важных исследовательских мероприятий в области информатики за последнее десятилетие.
В своей статье «Возможно конструктивные доказательства и исчисление высказываний» [7] , опубликованной в 1975 году, он представил эквациональную теорию PV (что означает «проверяемость за полиномиальное время»), чтобы формализовать понятие доказательств, используя только концепции полиномиального времени. Еще один важный вклад в эту область он внес в своей статье 1979 года совместно со своим учеником Робертом А. Рекхоу «Относительная эффективность систем пропозициональных доказательств» [8] , в которой они формализовали понятия p-симуляции и эффективной системы пропозициональных доказательств. , который положил начало области, которая сейчас называется сложностью доказательства высказываний . Они доказали, что существование системы доказательств, в которой каждая истинная формула имеет краткое доказательство, эквивалентно NP = coNP . Кук вместе со своим учеником Фуонгом Нгуеном стал соавтором книги в этой области под названием «Логические основы сложности доказательств». [9]
Его основными областями исследований являются теория сложности и сложность доказательств , а также экскурсы в семантику языков программирования , параллельные вычисления и искусственный интеллект . Другие области, в которые он внес свой вклад, включают ограниченную арифметику , ограниченную обратную математику , сложность функций высшего типа, сложность анализа и нижние границы в системах доказательства высказываний .
Он назвал класс сложности NC в честь Ника Пиппенджера . Его именем назван класс сложности SC . [10] Им же введено определение класса сложности AC 0 и его иерархии AC . [11]
По словам Дона Кнута, алгоритм KMP был вдохновлен автоматами Кука для распознавания составных палиндромов за линейное время . [12]
Кук был награжден Мемориальной стипендией Стейси NSERC EWR в 1977 году, исследовательской стипендией Киллама в 1982 году и получил премию CRM-Fields-PIMS в 1999 году. Он получил премию Джона Л. Синджа и медаль Бернарда Больцано, а также является членом Королевское общество Лондона и Королевское общество Канады . Кук был избран членом Национальной академии наук (США) и Американской академии искусств и наук . Он является членом-корреспондентом Геттингенской академии наук и гуманитарных наук .
Кук получил премию Тьюринга ACM в 1982 году. Ассоциация вычислительной техники удостоила его звания члена ACM в 2008 году за его фундаментальный вклад в теорию сложности вычислений . [13] Ассоциация символической логики выбрала его для чтения лекции Гёделя в 1999 году. [14]
В 2013 году правительство Онтарио наградило его Орденом Онтарио , высшей наградой Онтарио . [15] В 2012 году он выиграл золотую медаль Канады Герхарда Герцберга в области науки и техники , высшую награду для ученых и инженеров в Канаде. [16] Медаль Герцберга присуждается NSERC за «как устойчивое превосходство, так и общее влияние исследовательской работы, проводимой в Канаде в области естественных наук и техники». [17] В 2015 году он был удостоен звания кавалера Ордена Канады. [18]
Кук был удостоен премии BBVA Foundation Frontiers of Knowledge Award 2015 в категории «Информационные и коммуникационные технологии» «за его важную роль в определении того, что компьютеры могут и не могут эффективно решать», по словам жюри. Его работа, продолжает он, «оказала огромное влияние во всех областях, где сложные вычисления имеют решающее значение».
Кук руководил многочисленными студентами магистратуры, а 36 аспирантов получили степени под его руководством. [1]
Кук живет со своей женой в Торонто . У них двое сыновей, Гордон и Джеймс. [19]
