סטיבן קוק

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

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

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

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

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






הערות שוליים

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