Oral history interview with Stephen Cook

Abstract

Cook recounts his early interest in electronics and association with electronic cardiac pacemaker inventor Wilson Greatbatch, and his education at the University of Michigan and Harvard University. He describes his first position as an assistant professor of mathematics at the University of California, Berkeley, and his growing interest in problems of computational complexity preceding an influential 1971 presentation on “The Complexity of Theorem Proving Procedures” at the ACM SIGACT Symposium on the Theory of Computing. Cook discusses his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award for “contributions to the theory of computational complexity, including the concept of nondeterministic, polynomial-time completeness.” He also discusses the feasibility of solving the P versus NP Problem.