סטיבן קוק
קפיצה לניווט
קפיצה לחיפוש
 | |
| סטיבן ארתור קוק | |
| לידה | 14 בדצמבר 1939 (גיל: 84) |
|---|---|
| ענף מדעי | מדעי המחשב |
| מקום מגורים | קנדה וארצות הברית |
| תרומות עיקריות | |
|
NP-שלמות משפט קוק-לוין | |
סטיבן ארתור קוק (נולד ב-14 בדצמבר 1939), הוא מדען-מחשב ומתמטיקאי אמריקאי-קנדי שתרם רבות לתורת הסיבוכיות. כיום הוא פרופסור באוניברסיטת טורונטו.
מחקר
סטיבן קוק נחשב לאחד האבות המייסדים של תורת הסיבוכיות.
במאמרו מ-1971 "המורכבות של הוכחת משפט",[1][2] קוק טבע פורמלית את המושגים של רדוקציה פולינומית ובעיות NP-שלמות, והוכיח את קיומה של בעיה NP-שלמה על ידי שהראה שבעיית הספיקות היא NP-שלמה. משפט זה הוכח באופן עצמאי על ידי לאוניד לוין בברית המועצות, ולכן מכונה משפט קוק-לוין. המאמר גם מציג פורמלית את הבעיה המפורסמת במדעי המחשב, שאלת P=NP.
פרסים
קוק זכה בפרס טיורינג בשנת 1982 על תרומתו לתורת הסיבוכיות.
קישורים חיצוניים
אתר האינטרנט הרשמי של סטיבן קוק
- סטיבן קוק, באתר פרויקט הגנאלוגיה במתמטיקה
- סטיבן קוק, באתר dblp
- סטיבן קוק, באתר גוגל סקולר
- סטיבן קוק באתר פרס טיורינג (באנגלית)
- סטיבן קוק, באתר אנציקלופדיה בריטניקה (באנגלית)
הערות שוליים
- ^ "The Complexity of Theorem Proving Procedures", PDF file of a scanned version
- ^ "The Complexity of Theorem Proving Procedures", PDF file of a retyped version
קטגוריות:
- סגל אוניברסיטת קליפורניה בברקלי
- מדעני מחשב אמריקאים
- עמיתי ACM
- עמיתים זרים בחברה המלכותית
- בוגרי אוניברסיטת הרווארד
- מקבלי עיטור מסדר אונטריו
- קנדים חברי האקדמיה הלאומית למדעים של ארצות הברית
- זוכי פרס טיורינג
- זוכי פרס חזית הידע
- סגל אוניברסיטת טורונטו
- מדעני מחשב קנדים
- מתמטיקאים אמריקאים
- מתמטיקאים קנדים
- בוגרי אוניברסיטת מישיגן
- אמריקאים שנולדו ב-1939
- חברי האקדמיה למדעים ולאמנויות של גטינגן