Стивен Кук
Стивен Кук | |
---|---|
![]() | |
Лични подаци | |
Датум рођења | 14. децембар 1939. |
Место рођења | Буфало (Њујорк), САД |
Образовање | Универзитет Харвард, Универзитет Мичигена |
Званични веб-сајт | |
www |
Стивен Артур Кук (енгл. Stephen Arthur Cook рођен 1939, Буфало, Њујорк) је познати информатичар.
Кук је формализовао појам НП-комплетности у свом чувеном раду из 1971, Комплексност процедура за доказивање теорема, који је такође садржао Кукову теорему, доказ да је САТ проблем НП-комплетан. Овај рад је оставио нерешено највеће тренутно питање у теријском рачунарству - да ли су класе сложености П и НП еквивалентне.
Кук је добио Тјурингову награду 1982. за ово откриће. Образложење за награду гласи:
За његово унапређивање нашег разумевања сложености израчунавања на значајан и дубок начин. Његов рад, Комплексност процедура за доказивање теорема, представљен 1971. на АЦМ СИГАЦТ симпозијуму , је поставио основе за теорију НП-комплетности. Истраживање граница и природе класе НП-комплетних проблема, које је уследило је представљало једну од најактивнијих и најважнијих истраживачких активности у рачунарству током протекле деценије.
Кук је дипломирао 1961. на Универзитету у Мичигену. Магистрирао је на Харварду, 1962. а докторирао 1966. Од 1966. до 1970. је радио на Берклију. Прешао је на Универзитет у Торонту 1970.
Спољашње везе
[уреди | уреди извор]