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