Стивен Кук
From Wikipedia, the free encyclopedia
Remove ads
Стивен Артур Кук (енгл. рођен 1939, Буфало, Њујорк) је познати информатичар.
Кук је формализовао појам НП-комплетности у свом чувеном раду из 1971, Комплексност процедура за доказивање теорема, који је такође садржао Кукову теорему, доказ да је САТ проблем НП-комплетан. Овај рад је оставио нерешено највеће тренутно питање у теријском рачунарству - да ли су класе сложености П и НП еквивалентне.
Кук је добио Тјурингову награду 1982. за ово откриће. Образложење за награду гласи:
За његово унапређивање нашег разумевања сложености израчунавања на значајан и дубок начин. Његов рад, Комплексност процедура за доказивање теорема, представљен 1971. на АЦМ СИГАЦТ симпозијуму , је поставио основе за теорију НП-комплетности. Истраживање граница и природе класе НП-комплетних проблема, које је уследило је представљало једну од најактивнијих и најважнијих истраживачких активности у рачунарству током протекле деценије.
Кук је дипломирао 1961. на Универзитету у Мичигену. Магистрирао је на Харварду, 1962. а докторирао 1966. Од 1966. до 1970. је радио на Берклију. Прешао је на Универзитет у Торонту 1970.
Remove ads
Спољашње везе
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads