สตีเฟน คุก โอซีโอนท์
เชฟในปี 2008
เกิด	สตีเฟน อาร์เธอร์ คุก ( 1939-12-14 ) 14 ธันวาคม 1939 บัฟฟาโลรัฐนิวยอร์ก
การศึกษา	มหาวิทยาลัยมิชิแกน ( ปริญญาตรี ) มหาวิทยาลัยฮาร์วาร์ด ( ปริญญาโท , ปริญญาเอก )
เป็นที่รู้จัก ในด้าน	ความสมบูรณ์แบบ NP ความซับซ้อนของการพิสูจน์เชิงประพจน์ ทฤษฎีบท คุก-เลวิน
รางวัล	รางวัลทัวริง(1982) การบรรยายของเกอเดล(1999) รางวัล CRM-Fields-PIMS (ปี 1999) รางวัลจอห์น แอล. ซินจ์(ปี 2006) เหรียญรางวัลเบอร์นาร์ด โบลซาโน(ปี 2008) เกอร์ฮาร์ด เฮิร์ซเบิร์ก เหรียญทองแคนาดา สาขาวิทยาศาสตร์และวิศวกรรม(ปี 2012) เครื่องราชอิสริยาภรณ์ชั้นเจ้าหน้าที่แห่งแคนาดา(ปี 2015) รางวัล BBVA Foundation Frontiers of Knowledge Award (ปี 2015)
เส้นทางอาชีพด้านวิทยาศาสตร์
ฟิลด์	วิทยาการคอมพิวเตอร์
สถาบันต่างๆ	มหาวิทยาลัยโทรอนโตมหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์
วิทยานิพนธ์	ในเรื่องเวลาการคำนวณขั้นต่ำของฟังก์ชัน(1966)
อาจารย์ที่ปรึกษาปริญญาเอก	ห่าวหวาง
นักศึกษาปริญญาเอก	Mark Braverman [ 1 ] Toniann Pitassi Walter Savitch Arvind Gupta Anna Lubiw

สตีเฟน อาร์เธอร์ คุก (เกิด 14 ธันวาคม 1939) เป็น นักวิทยาศาสตร์คอมพิวเตอร์ และนักคณิตศาสตร์ ชาวอเมริกัน-แคนาดาผู้มีผลงานสำคัญในสาขาทฤษฎีความซับซ้อนและความซับซ้อนของการพิสูจน์ ปัจจุบันดำรง ตำแหน่งศาสตราจารย์กิตติคุณประจำมหาวิทยาลัยโทรอนโตภาควิชาวิทยาการคอมพิวเตอร์และภาควิชาคณิตศาสตร์

คุกได้รับการยกย่องว่าเป็นหนึ่งในผู้บุกเบิกทฤษฎีความซับซ้อนของการคำนวณเขาได้รับรางวัล ACM Turing Award ในปี 1982

คุกได้รับปริญญาตรีในปี 1961 จากมหาวิทยาลัยมิชิแกนและปริญญาโทและปริญญาเอกจากมหาวิทยาลัยฮาร์วาร์ดในปี 1962 และ 1966 ตามลำดับ จากภาควิชาคณิตศาสตร์^{[ 2 ]}เขาเข้าร่วม ภาควิชาคณิตศาสตร์ ของมหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์ในปี 1966 ในตำแหน่งผู้ช่วยศาสตราจารย์ และอยู่ที่นั่นจนถึงปี 1970 เมื่อเขาไม่ได้รับการต่อสัญญา ในสุนทรพจน์ฉลองครบรอบ 30 ปีของภาควิชาวิศวกรรมไฟฟ้าและวิทยาการคอมพิวเตอร์ของเบิร์กลี ย์ ริชาร์ด คาร์ป ผู้ได้รับ รางวัลทัวริงและศาสตราจารย์ของเบิร์กลีย์กล่าวว่า "เป็นความอับอายอย่างที่สุดของเราที่ไม่สามารถโน้มน้าวให้ภาควิชาคณิตศาสตร์ให้ตำแหน่งถาวรแก่เขาได้" ^{[ 3 ]}คุกเข้าร่วมคณะของมหาวิทยาลัยโตรอนโต ภาควิชา วิทยาการคอมพิวเตอร์และคณิตศาสตร์ในปี 1970 ในตำแหน่งรองศาสตราจารย์ ซึ่งเขาได้รับการเลื่อนตำแหน่งเป็นศาสตราจารย์ในปี 1975 และศาสตราจารย์เกียรติคุณในปี 1985

ในระหว่างการศึกษาปริญญาเอก คุกได้ทำงานเกี่ยวกับความซับซ้อนของฟังก์ชัน โดยเฉพาะอย่างยิ่งการคูณ ในบทความสำคัญปี 1971 ของเขาเรื่อง "ความซับซ้อนของขั้นตอนการพิสูจน์ทฤษฎีบท" ^{[ 4 ]}คุกได้กำหนดแนวคิดของการลดเวลาพหุนาม (หรือที่รู้จักกันในชื่อการลดแบบคุก ) และความสมบูรณ์ของ NP อย่างเป็นทางการและพิสูจน์การมีอยู่ของ ปัญหา ที่สมบูรณ์แบบของ NPโดยแสดงให้เห็นว่าปัญหาความพึงพอใจของบูลีน (โดยทั่วไปรู้จักกันในชื่อ SAT) เป็น ปัญหา ที่สมบูรณ์แบบของ NPทฤษฎีบทนี้ได้รับการพิสูจน์โดยอิสระโดยลีโอนิด เลวินในสหภาพโซเวียตและจึงได้รับชื่อว่าทฤษฎีบทคุก-เลวินบทความนี้ยังได้กำหนดปัญหาที่มีชื่อเสียงที่สุดในวิทยาศาสตร์คอมพิวเตอร์ นั่นคือปัญหา P เทียบกับ NPอย่างไม่เป็นทางการ คำถาม "P เทียบกับ NP" ถามว่าปัญหาการเพิ่มประสิทธิภาพทุกปัญหาที่มีคำตอบที่สามารถตรวจสอบความถูกต้อง/ความเหมาะสมได้อย่างมีประสิทธิภาพ สามารถแก้ไขได้อย่างเหมาะสมด้วยอัลกอริทึมที่มีประสิทธิภาพหรือไม่ เนื่องจากปัญหาการหาค่าที่เหมาะสมที่สุดในลักษณะนี้มีอยู่มากมายในชีวิตประจำวัน คำตอบที่เป็นบวกสำหรับคำถาม "P เทียบกับ NP" จึงน่าจะมีผลกระทบอย่างลึกซึ้งทั้งในทางปฏิบัติและทางปรัชญา

คุกตั้งข้อสันนิษฐานว่ามีปัญหาการหาค่าเหมาะสมที่สุด (ที่มีวิธีแก้ปัญหาที่ตรวจสอบได้ง่าย) ที่ไม่สามารถแก้ไขได้ด้วยอัลกอริทึมที่มีประสิทธิภาพ กล่าวคือ P ไม่เท่ากับ NP ข้อสันนิษฐานนี้ได้ก่อให้เกิดการวิจัยมากมายในทฤษฎีความซับซ้อนของการคำนวณซึ่งได้ปรับปรุงความเข้าใจของเราเกี่ยวกับความยากลำบากโดยธรรมชาติของปัญหาการคำนวณและสิ่งที่สามารถคำนวณได้อย่างมีประสิทธิภาพ อย่างไรก็ตาม ข้อสันนิษฐานนี้ยังคงเปิดอยู่และเป็นหนึ่งในเจ็ดปัญหา Millennium Prizeที่ มีชื่อเสียง ^{[ 5 ] [ 6 ]}

ในปี 1982 คุกได้รับรางวัลทัวริง (Turing Award) สำหรับผลงานของเขาในด้านทฤษฎีความซับซ้อน คำประกาศเกียรติคุณของเขามีดังนี้:

ด้วยผลงานอันล้ำลึกและสำคัญยิ่งของเขา ทำให้เราเข้าใจถึงความซับซ้อนของการคำนวณได้ดียิ่งขึ้น บทความสำคัญของเขาเรื่อง " ความซับซ้อนของกระบวนการพิสูจน์ทฤษฎีบท"ซึ่งนำเสนอในการประชุม ACM SIGACT Symposium on the Theory of Computing ปี 1971 ได้วางรากฐานให้กับทฤษฎี NP-Completeness การสำรวจขอบเขตและธรรมชาติของปัญหาในกลุ่ม NP-complete ที่ตามมานั้น เป็นหนึ่งในกิจกรรมการวิจัยที่สำคัญและคึกคักที่สุดในสาขาวิทยาการคอมพิวเตอร์ในช่วงทศวรรษที่ผ่านมา

ในบทความ "Feasibly Constructive Proofs and the Propositional Calculus" ^{[ 7 ]}ที่ตีพิมพ์ในปี 1975 เขาได้แนะนำทฤษฎีสมการ PV (ย่อมาจาก Polynomial-time Verifiable) เพื่อทำให้แนวคิดของการพิสูจน์เป็นทางการโดยใช้เพียงแนวคิดเวลาพหุนามเท่านั้น เขาได้สร้างคุณูปการสำคัญอีกครั้งในสาขานี้ในบทความปี 1979 ร่วมกับนักศึกษาของเขาRobert A. Reckhowเรื่อง "The Relative Efficiency of Propositional Proof Systems" ^{[ 8 ]}ซึ่งพวกเขาได้ทำให้แนวคิดของการจำลอง pและระบบพิสูจน์เชิงประพจน์ ที่มีประสิทธิภาพเป็นทางการ ซึ่งเป็นจุดเริ่มต้นของสาขาที่เรียกว่าความซับซ้อนของการพิสูจน์ เชิงประพจน์ พวกเขาพิสูจน์ว่าการมีอยู่ของระบบพิสูจน์ที่ทุกสูตรที่เป็นจริงมีการพิสูจน์สั้นๆ นั้นเทียบเท่ากับNP = coNP Cook ได้ร่วมเขียนหนังสือกับนักศึกษาของเขาPhuong The Nguyenในสาขานี้ในชื่อ "Logical Foundations of Proof Complexity" ^{[ 9 ]}

งานวิจัยหลักของเขาคือทฤษฎีความซับซ้อนและความซับซ้อนของการพิสูจน์โดยมีการศึกษาเพิ่มเติมในด้านความหมายของภาษาโปรแกรมการคำนวณแบบขนานและปัญญาประดิษฐ์สาขาอื่นๆ ที่เขามีส่วนร่วม ได้แก่เลขคณิตแบบมีขอบเขตคณิตศาสตร์ย้อนกลับแบบมีขอบเขต ความซับซ้อนของฟังก์ชันประเภทสูงความซับซ้อนของการวิเคราะห์และขอบเขตล่างในระบบการพิสูจน์เชิง ประพจน์

คุกได้รับรางวัลNSERC EWR Steacie Memorial Fellowship ในปี 1977, รางวัล Killam Research Fellowship ในปี 1982 และได้รับรางวัล CRM-Fields-PIMSในปี 1999 เขาได้รับรางวัล John L. Synge Awardและเหรียญ Bernard Bolzanoจากสถาบันวิทยาศาสตร์แห่งเช็ก (2008) ^{[ 13 ]}และเป็นสมาชิกของราชสมาคมแห่งลอนดอนและราชสมาคมแห่งแคนาดาคุกได้รับเลือกให้เป็นสมาชิกของสถาบันวิทยาศาสตร์แห่งชาติ (สหรัฐอเมริกา) และสถาบันศิลปะและวิทยาศาสตร์แห่งอเมริกาเขาเป็นสมาชิกสมทบของสถาบันวิทยาศาสตร์และมนุษยศาสตร์แห่งเกิตติงเงน

คุกได้รับรางวัล ACM Turing Awardในปี 1982 สมาคมเครื่องจักรคำนวณ (Association for Computing Machinery)ยกย่องเขาให้เป็น Fellow ของACMในปี 2008 สำหรับ ผลงานพื้นฐานของเขาในทฤษฎีความซับซ้อนของการคำนวณ [ ^{14 ] เขา} ได้รับเลือกจากสมาคมตรรกะเชิงสัญลักษณ์ (Association for Symbolic Logic)ให้บรรยายGödel Lectureในปี 1999 ^{[ 15 ]}

รัฐบาลออนแทรีโอแต่งตั้งเขาให้ดำรงตำแหน่งในเครื่องราชอิสริยาภรณ์แห่งออนแทรีโอในปี 2013 ซึ่งเป็นเกียรติสูงสุดในออนแทรีโอ^{[ 16 ]}เขาได้รับรางวัลเหรียญทอง Gerhard Herzberg Canada สำหรับวิทยาศาสตร์และวิศวกรรม ในปี 2012 ซึ่งเป็น เกียรติสูงสุดสำหรับนักวิทยาศาสตร์และวิศวกรในแคนาดา^{[ 17 ]}เหรียญ Herzberg มอบโดยNSERCสำหรับ "ความเป็นเลิศอย่างต่อเนื่องและอิทธิพลโดยรวมของงานวิจัยที่ดำเนินการในแคนาดาในสาขาวิทยาศาสตร์ธรรมชาติหรือวิศวกรรม" ^{[ 18 ]}เขาได้รับการแต่งตั้งเป็นเจ้าหน้าที่แห่งเครื่องราชอิสริยาภรณ์แคนาดาในปี 2015 ^{[ 19 ] [ 20 ]}

คุกได้รับรางวัล BBVA Foundation Frontiers of Knowledge Awardประจำปี 2015 ในสาขาเทคโนโลยีสารสนเทศและการสื่อสาร "สำหรับบทบาทสำคัญของเขาในการระบุว่าคอมพิวเตอร์สามารถและไม่สามารถแก้ปัญหาอะไรได้อย่างมีประสิทธิภาพ" ตามคำกล่าวของคณะกรรมการตัดสิน งานของเขา "มีผลกระทบอย่างมากในทุกสาขาที่การคำนวณที่ซับซ้อนมีความสำคัญ"

คุกได้ดูแลนักศึกษาปริญญาโทจำนวนมาก และนักศึกษาปริญญาเอก 36 คนสำเร็จการศึกษาภายใต้การดูแลของเขา^{[ 1 ]}

คุกอาศัยอยู่กับภรรยาของเขาในโตรอนโตพวกเขามีลูกชายสองคน หนึ่งในนั้นคือกอร์ดอน คุกนัก แล่นเรือใบโอลิมปิก ^{[ 21 ]}

• รายชื่อผู้บุกเบิกในสาขาวิทยาการคอมพิวเตอร์

วิกิมีเดียคอมมอน ส์มีสื่อที่เกี่ยวข้องกับสตีเฟน คุก

• หน้าหลักของ Stephen A. Cook
• 'P เทียบกับ NP' และข้อจำกัดของการคำนวณ – การบรรยายสาธารณะโดย สตีเฟน คุก ที่มหาวิทยาลัยโทรอนโต
• การสัมภาษณ์ประวัติศาสตร์ปากเปล่ากับสตีเฟน คุกที่สถาบันชาร์ลส์ แบ็บเบจมหาวิทยาลัยมินนิโซตา คุกได้พูดคุยเกี่ยวกับประวัติการศึกษาของเขาที่มหาวิทยาลัยมิชิแกนและมหาวิทยาลัยฮาร์วาร์ด และงานในช่วงแรกที่มหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์ รวมถึงความสนใจที่เพิ่มขึ้นของเขาในปัญหาเกี่ยวกับความซับซ้อนของการคำนวณ คุกเล่าถึงการย้ายไปมหาวิทยาลัยโตรอนโตในปี 1970 และการตอบรับงานวิจัยของเขาเกี่ยวกับ NP-completeness ซึ่งนำไปสู่การได้รับรางวัล AM Turing Award
• สตีเฟน อาร์เธอร์ คุกจากโครงการลำดับวงศ์ตระกูลทางคณิตศาสตร์
• Stephen A. Cook ที่DBLP Bibliography Server