Loading AI tools
מדען מחשב ומתמטיקאי קנדי-אמריקאי מוויקיפדיה, האנציקלופדיה החופשית
סטיבן ארתור קוק (נולד ב-14 בדצמבר 1939), הוא מדען-מחשב ומתמטיקאי אמריקאי-קנדי שתרם רבות לתורת הסיבוכיות. כיום הוא פרופסור באוניברסיטת טורונטו.
![]() | |
סטיבן ארתור קוק | |
לידה |
14 בדצמבר 1939 (בן 84) באפלו, ארצות הברית ![]() |
---|---|
שם לידה |
Stephen Arthur Cook ![]() |
ענף מדעי | מדעי המחשב |
מקום מגורים | קנדה וארצות הברית |
מקום לימודים | |
מנחה לדוקטורט |
האו ואנג ![]() |
מוסדות | |
תלמידי דוקטורט |
Toniann Pitassi, Leslie Michael Goldschlager, Derek C. Oppen, Daniel Brand, Steven Perron, Tsuyoshi Morioka, Phuong The Nguyen, Tomoyuki Yamakami, Martin Dowd, Stephen Bellantoni, Lila A. Fontes, R. Dustin Wehr, Gloria Kissin, Dai Tri Man Le, Robert A. Reckhow, Akitoshi Kawamura, Kaveh Ghasemloo, Alan Ramsay Skelley, Antonina Kolokolova, ארבינד גופטה, Michael Soltys, H. James (Howard) Hoover, ולטר סאביץ', Anna Lubiw, מרק ברברמן, Roberto Lins de Carvalho, Paul William Beame, Valentine Kabanets, Xudong Fu, Patrick William Dymond, Romas Aleliunas, Pierre Murdock McKenzie, François Pitt, Bruce M. Kapron, Robert Robere ![]() |
פרסים והוקרה |
|
צאצאים |
גורדון קוק ![]() |
www | |
תרומות עיקריות | |
NP-שלמות משפט קוק-לוין | |
![]() ![]() |
סטיבן קוק נחשב לאחד האבות המייסדים של תורת הסיבוכיות.
במאמרו מ-1971 "המורכבות של הוכחת משפט",[1][2] קוק טבע פורמלית את המושגים של רדוקציה פולינומית ובעיות NP-שלמות, והוכיח את קיומה של בעיה NP-שלמה על ידי שהראה שבעיית הספיקות היא NP-שלמה. משפט זה הוכח באופן עצמאי על ידי לאוניד לוין בברית המועצות, ולכן מכונה משפט קוק-לוין. המאמר גם מציג פורמלית את הבעיה המפורסמת במדעי המחשב, שאלת P=NP.
קוק זכה בפרס טיורינג בשנת 1982 על תרומתו לתורת הסיבוכיות.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.