סטיבן קוק

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

פרס טיורינג לשנת 1982

סטיבן ארתור קוק (נולד ב-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