סטיבן קוק

סטיבן ארתור קוק
Stephen Cook
	סטיבן ארתור קוק
לידה	14 בדצמבר 1939 (בן 85); באפלו, ארצות הברית
שם לידה	Stephen Arthur Cook
מדינה	קנדה וארצות הברית
ענף מדעי	מדעי המחשב
השכלה	אוניברסיטת הרווארד; אוניברסיטת מישיגן ;
מנחה לדוקטורט	האו ואנג
תארים	דוקטור למדעים
תלמידי דוקטורט	Toniann Pitassi, Leslie Michael Goldschlager, Phuong The Nguyen, R. Dustin Wehr, ארבינד גופטה, Michael Soltys, H. James (Howard) Hoover, ולטר סאביץ', Anna Lubiw, מרק ברברמן, בפסקה זו 25 רשומות נוספות שטרם תורגמו
ילדים	גורדון קוק
פרסים והוקרה	עמית החברה המלכותית; פרס חזית הידע של קרן BBVA (2015); עמית ACM (2008); עמית החברה המלכותית של קנדה; מדליית הזהב של קנדה ע״ש גרהרד הרצברג למדע והנדסה (2012); קצין במסדר קנדה (2015); Gödel Lecturer (1999); מסדר אונטריו (2013); פרס טיורינג (1982); פרס מרכז מחקר המתמטיקה הקנדי-פילדס-המכון הפסיפי למדעים מתמטיים (1999); John L. Synge Award (2006) ;
	www.cs.toronto.edu/~sacook/
תרומות עיקריות
	NP-שלמות משפט קוק-לוין

סטיבן ארתור קוק (נולד ב-14 בדצמבר 1939), הוא מדען-מחשב ומתמטיקאי אמריקאי-קנדי שתרם רבות לתורת הסיבוכיות. כיום הוא פרופסור באוניברסיטת טורונטו.

מחקר

סטיבן קוק נחשב לאחד האבות המייסדים של תורת הסיבוכיות.

במאמרו מ-1971 "המורכבות של הוכחת משפט",^[1]^[2] קוק טבע פורמלית את המושגים של רדוקציה פולינומית ובעיות NP-שלמות, והוכיח את קיומה של בעיה NP-שלמה על ידי שהראה שבעיית הספיקות היא NP-שלמה. משפט זה הוכח באופן עצמאי על ידי לאוניד לוין בברית המועצות, ולכן מכונה משפט קוק-לוין. המאמר גם מציג פורמלית את הבעיה המפורסמת במדעי המחשב, שאלת P=NP.

פרסים

קוק זכה בפרס טיורינג בשנת 1982 על תרומתו לתורת הסיבוכיות.

קישורים חיצוניים

מדיה וקבצים בנושא סטיבן קוק בוויקישיתוף

אתר האינטרנט הרשמי של סטיבן קוק
סטיבן קוק, באתר פרויקט הגנאלוגיה במתמטיקה
סטיבן קוק, באתר dblp
סטיבן קוק, באתר ResearchGate
סטיבן קוק, באתר גוגל סקולר
סטיבן קוק באתר פרס טיורינג (באנגלית)
סטיבן קוק, באתר אנציקלופדיה בריטניקה (באנגלית)

הערות שוליים

^ "The Complexity of Theorem Proving Procedures", PDF file of a scanned version
^ "The Complexity of Theorem Proving Procedures", PDF file of a retyped version

[1] "The Complexity of Theorem Proving Procedures", PDF file of a scanned version

[2] "The Complexity of Theorem Proving Procedures", PDF file of a retyped version

[1]

[2]