Стивен Кук: автор самой знаменитой открытой задачи информатики

Стивен Кук родился в Буффало, штат Нью-Йорк, учился в Гарварде и начинал карьеру в Калифорнийском университете в Беркли. Там ему не дали постоянной должности, и в 1970 году Кук перебрался в Торонтский университет, где и прошла вся его дальнейшая научная карьера. Через год вышла его статья о сложности доказательства теорем.

Суть его открытия в том, что огромное число практических задач, от составления расписаний до поиска маршрутов, оказываются в некотором смысле одной и той же задачей. Если найти быстрый алгоритм хотя бы для одной из них, быстро решатся и все остальные. Независимо от Кука к тому же результату пришёл советский математик Леонид Левин, поэтому сегодня говорят о теореме Кука — Левина. В 1982 году Кук получил премию Тьюринга, высшую награду в информатике.

От ответа на вопрос «P = NP?» зависит, например, надёжность современных шифров, поэтому Математический институт Клэя включил его в список задач тысячелетия. Фамилия Кук — английская и означает «повар». На сайте десять известных её носителей, среди них — мореплаватель Джеймс Кук и австралийский премьер Джозеф Кук.