סטיבן קוק

מתוך המכלול, האנציקלופדיה היהודית
(הופנה מהדף סטפן קוק)
קפיצה לניווט קפיצה לחיפוש


שגיאות פרמטריות בתבנית:מדען

פרמטרים [ פרסים והנצחה, ארצות מגורים ] לא מופיעים בהגדרת התבנית

סטיבן ארתור קוק
Prof.Cook.jpg
סטיבן ארתור קוק
לידה 14 בדצמבר 1939 (גיל: 81)
ענף מדעי מדעי המחשב
תרומות עיקריות
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
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0