Stephen Cook
hoạt động khoảng năm 1939, Buffalo, New York, Hoa Kỳ
Nhà khoa học máy tính và toán học người Mỹ-Canada, người sáng lập lý thuyết NP-đầy đủ, đặt ra câu hỏi P so với NP và chứng minh định lý Cook–Levin.
Stephen Cook sinh tại Buffalo, New York, và nhận bằng tiến sĩ toán học tại Đại học Harvard năm 1966. Sau thời gian làm trợ lý giáo sư tại Đại học California, Berkeley, ông gia nhập Đại học Toronto năm 1970, nơi ông gắn bó suốt sự nghiệp và nhập quốc tịch Canada.
Bài báo năm 1971 của Cook, "The Complexity of Theorem-Proving Procedures", đưa ra khái niệm NP-đầy đủ và chứng minh bài toán thỏa mãn Boole (SAT) là NP-đầy đủ — định lý Cook–Levin, được Leonid Levin ở Liên Xô độc lập khám phá. Bài báo đặt nền cho câu hỏi P so với NP: liệu mọi bài toán mà lời giải có thể kiểm tra nhanh có thể giải nhanh hay không. Nó khai sinh lĩnh vực lý thuyết độ phức tạp tính toán và vẫn là một trong bảy Bài toán Thiên niên kỷ Clay, đến nay còn để ngỏ.
Với công trình này Cook nhận giải thưởng Turing của ACM năm 1982, vinh dự cao nhất trong khoa học máy tính. Ông tiếp tục nghiên cứu lý thuyết độ phức tạp và độ phức tạp chứng minh tại Đại học Toronto, nơi ông hiện là Giáo sư Danh dự.
Nơi làm việc: Đại học California, Berkeley, Đại học Toronto
Canada, Hoa Kỳ