Стівен Артур Кук: біографія

У своїй роботі«The Complexity of Theorem Proving Procedures»Кук довів, що завдання здійсненності булевих формул є NP-повною. Тим самим він порушив питання про рівність класів складності P і NP, один з найскладніших питань теорії обчислювальних систем, на який до цих пір немає відповіді.

Біографія

Кук отримав титул бакалавра в Мічиганському університеті в 1961 році. Рік по тому він отримав ступінь магістра наук в Гарварді, де в 1966 році досяг ступеня доктора філософії. До 1970 року працював асистентом (англ.assistant professor) з математики в Берклі, де так і не набув статусу постійного співробітника. Річард Карп, лауреат премії Тьюрінга 1985 року, скаже про це

n

Це назавжди залишиться нашою провиною, що ми не змогли умовити факультет математики дати йому цей статус. N

n

Оригінальний текст(англ.)

n

n

It is to our everlasting shame that we were unable to persuade the math department to give him tenure.

n

n

n

n

- Річард Карп до 30-річчя факультету інформатики Берклі

n

Цю честь йому надав Торонтський університет, призначивши Стівена Кука професором в 1975 році.

Нагороди

• 1982 - Премія Тюрінга «За вагомий прогрес, досягнутий їм у розумінні складності обчислень. Його робота поклала основу теорії NP-повноти. Дослідження властивостей і меж цього класу стало одним з найважливіших напрямків теорії обчислювальних систем за останні десять років. "

Комментарии

Сайт: Википедия