סטיבן קוק

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

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

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

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

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

הערות שוליים

סגל אוניברסיטת קליפורניה בברקלי
מדעני מחשב אמריקאים
עמיתי ACM
עמיתים זרים בחברה המלכותית
בעלי תואר דוקטור מאוניברסיטת הרווארד
מקבלי עיטור מסדר אונטריו
קנדים חברי האקדמיה הלאומית למדעים של ארצות הברית
זוכי פרס טיורינג
זוכי פרס חזית הידע
סגל אוניברסיטת טורונטו
מדעני מחשב קנדים
מתמטיקאים אמריקאים
מתמטיקאים קנדים
בוגרי אוניברסיטת מישיגן
אמריקאים שנולדו ב-1939
חברי האקדמיה למדעים ולאמנויות של גטינגן