Стивен Кук - Stephen Cook
Стивен Кук | |
---|---|
Родился |
Стивен Артур Кук
14 декабря 1939 г. |
Альма-матер |
Гарвардский университет Мичиганского университета |
Известен |
NP-полнота Утвержденная сложность доказательства теоремы Кука – Левина |
Награды |
Премия Тьюринга (1982) Премия CRM-Fields-PIMS (1999) Премия Джона Л. Синджа (2006) Медаль Бернарда Больцано Герхард Герцберг, Канада, Золотая медаль в области науки и техники (2012) Кавалер Ордена Канады (2015) BBVA Foundation Frontiers of Knowledge Премия (2015) |
Научная карьера | |
Поля | Информатика |
Учреждения |
Университет Торонто Калифорнийский университет, Беркли |
Тезис | О минимальном времени вычисления функций (1966 г.) |
Докторант | Хао Ван |
Докторанты |
Марк Браверман Тониан Питасси Уолтер Савич Арвинд Гупта Анна Любив |
Стивен Артур Кук , О.К. , Онтарио (родился 14 декабря 1939 г.), американо-канадский ученый - компьютерщик и математик , внесший большой вклад в теорию сложности и сложность доказательств . Он является профессором университета в Университете Торонто , факультет компьютерных наук и факультета математики .
биография
Кук получил степень бакалавра в 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 аспиранта получили степень под его руководством.
Личная жизнь
Кук живет с женой в Торонто . У них двое сыновей, Гордон и Джеймс . Он играет на скрипке и любит плавать . Его часто называют коротким именем Стив Кук.
Смотрите также
использованная литература
внешние ссылки
- Домашняя страница Стивена А. Кука
- «P против NP» и пределы вычислений - публичная лекция Стивена Кука в Университете Торонто
- Устное интервью истории со Стивеном Куком в Институте Чарльза Бэббиджа , Университет Миннесоты. Кук рассказал о своем образовании в Мичиганском и Гарвардском университетах, а также о своей ранней работе в Калифорнийском университете в Беркли и о своем растущем интересе к проблемам вычислительной сложности. Кук рассказал о своем переезде в Университет Торонто в 1970 году и о приеме его работы по NP-полноте, которая привела к его Премии AM Тьюринга.
- Стивен Артур Кук на проекте « Математическая генеалогия»
- Стивен А. Кук на сервере библиографии DBLP