Stephen Cook
Stephen Arthur Cook (ur. 14 grudnia 1939 w Buffalo, Nowy Jork[1]) – amerykański informatyk, za wkład w rozwój teorii złożoności obliczeniowej otrzymał nagrodę Turinga w 1982 roku[1].
Życiorys
[edytuj | edytuj kod]Ojciec Cooka pracował jako chemik w filii Union Carbide, a także był adiunktem w SUNY Buffalo[2]. Jego matka pracowała jako gospodyni domowa, a także jako nauczycielka języka angielskiego w Erie Community College[2]. W wieku 10 lat przeprowadził się wraz z rodziną do Clarence w stanie Nowy Jork[2]. Jako nastolatek zainteresował się elektroniką i pracował dla Wilsona Greatbatcha[2].
Cook rozpoczął studia na Uniwersytecie Michigan w 1957 roku na kierunku inżynieria nauk ścisłych[2]. Zmienił kierunek na matematykę i uzyskał tytuł licencjata w 1961 roku[2]. Następnie rozpoczął studia podyplomowe na Wydziale Matematyki Uniwersytetu Harvarda[2]. Cook uzyskał raz tytuł magistra (1962) i doktorat (1966) w dziedzinie informatyki na Uniwersytecie Harvarda[1].
Jego praca magisterska zatytułowana O minimalnym czasie obliczania funkcji dotyczy wewnętrznej złożoności obliczeniowej mnożenia[2]. Jednym z wkładów było ulepszenie algorytmu mnożenia Andrei Tooma, znanego obecnie jako Toom–Cook multiplication[2]. Algorytm ten jest nadal przedmiotem badań i ma praktyczne znaczenie w arytmetyce o wysokiej precyzji[2].
Po opuszczeniu Harvardu podjął pracę na wydziale Uniwersytetu Kalifornijskiego w Berkeley[1].
W 1970 Cook przeniósł się na Uniwersytet w Toronto, gdzie w 1985 został profesorem nadzwyczajnym[1][2]. W 1971 roku Cook opublikował „The Complexity of Theorem Proving Procedures”, przełomowy artykuł, który położył podwaliny pod teorię problemów NP-zupełnych – problemów, dla których nie jest znany skuteczny algorytm rozwiązania[1][2]. Cook wykazał, że niektóre problemy w NP, znane obecnie jako problemy NP-zupełne, są tak samo trudne do rozwiązania jak inne w NP, w tym sensie, że jeśli którykolwiek z tych problemów jest łatwy do rozwiązania, to wszystkie problemy w NP są łatwe do rozwiązania[2].
Cook opracował metodę redukcji ograniczonej zasobami[2]. Technika ta jest podstawowym narzędziem w teorii złożoności obliczeniowej i stanowi podstawę w bezpieczeństwie kryptograficznym opartym na złożoności[2].
Cook miał również duży wpływ w dziedzinach, jak teoria automatów, obliczenia równoległe, semantyka i weryfikacja języka programu, algebra obliczeniowa oraz obliczalność[2].
Cook jest członkiem Royal Society of London, Royal Society of Canada, U.S. National Academy of Sciences oraz American Academy of Arts and Sciences[1]. Był stypendystą NSERC Steacie w latach 1978-79, otrzymał stypendium Killam Research Fellowship w latach 1982-83 i wiele nagród[2].
Obecnie mieszka w Toronto z żoną Lindą i ma dwóch synów[2]. Jest żeglarzem i wieloletnim członkiem Royal Canadian Yacht Club[2].