An Interview with Stephen A. Cook

Philip L. Frana
The Ch arl es Babb age Instit ute holds one of the world’s largest collections of research- grade oral history interviews relating to the history of computers, software, and networking. Most of the 400 interviews have been conducted in the context of specific research projects, which facilitate the interviewer’s extensive preparation and often suggest specific lines of questions. Transcripts from these oral histories are a key source in understanding the history of computing, since traditional historical sources are frequently incomplete.
The following is a condensed version of an interview with A.M. Turing Award recipient and ACM Fellow Stephen A. Cook, considered one of the forefathers of computational complexity theory. The original interview was conducted by CBI researcher Philip L. Frana in Toronto, Canada, in 2002 following Cook’s lecture at the University of Minnesota as part of the Cray Distinguished Speaker Series. After describing his background, including his influential 1971 presentation on “The Complexity of Theorem Proving Procedures,” Cook discusses his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his 1982 A.M. Turing Award for “contributions to the theory of computational complexity, including the concept of nondeterministic, polynomial- time completeness. The ensuing exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science.”
january 2012 | vol . 55 | no. 1 | communications of the ACM
Read full text