סטיבן קוק

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
סטיבן ארתור קוק
Prof.Cook.jpg
סטיבן ארתור קוק
לידה 14 בדצמבר 1939 (גיל: 82)
ענף מדעי מדעי המחשב
מקום מגורים קנדה וארצות הברית
תרומות עיקריות
NP-שלמות
משפט קוק-לוין

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

מחקר

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

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

פרסים

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

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

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

הערות שוליים

  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
Logo hamichlol.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0