14 декабря 1939 года родился ученый Стивен Кук Он один из основоположников теории сложности вычислений

После окончания Мичиганского университета Стивен поступил в Гарвард, где в 1966 году получил степень доктора философии. До 1970 года Кук работал ассистентом на математическом факультете Калифорнийского университета в Беркли, но за несколько лет он так и не получил степень профессора. К тридцатилетию факультета информатики в Беркли лауреат премии Тьюринга Ричард Карп заявил: «К нашему стыду мы не смогли уговорить факультет математики дать Стивену этот статус». Годы спустя Кук все же стал профессором, правда, в университете Торонто.

Основные области исследований Стивена Кука – искусственный интеллект, теория сложности и семантика языков программирования. В 1982 году «за существенный прогресс, достигнутый им в понимании сложности вычислений» Стивен Кук был получил премию Тьюринга. Его труды легли в основу теории NP-полноты. Исследование границ и свойств этого класса стало одним из главных направлений теории вычислительных систем за последние десять лет.

В своей статье «Сложность процедур доказательства теорем» Кук описал понятия NP-полноты и редукции за полиномиальное время, а также доказал существование NP-полной проблемы, показав, что задача логической выполнимости является NP-полной. Ранее данная теорему доказал советский ученый Леонид Левин, и поэтому сегодня она называется теоремой Кука-Левина.