Contents
Stephen Cook
Establishing a foundation of NP-completeness theory.
The Complexity of Theorem Proving Procedures · Proof complexity
- Born
- 14 December 1939
- Birthplace
- Buffalo
More people
Stephen Cook
American-Canadian computer scientist whose research clarified how problems can be compared by computational difficulty. His 1971 work on satisfiability became a central reference point in complexity theory.
Early life
Mathematical education
Studied at Michigan before completing a master’s degree and doctorate at Harvard. His doctoral research examined the complexity of arithmetic functions.
Career
- 1966
Berkeley appointment
Joined the mathematics faculty.
- 1970
Toronto move
Joined the computer science and mathematics departments.
- 1982
Turing Award
Received computing’s major research honour for complexity theory.
Contributions
The Complexity of Theorem Proving Procedures
Established Boolean satisfiability as an NP-complete problem.
Proof complexity
Investigated the resources required by formal proofs.
Beyond work
Family life
Settled in Toronto with his family. His son Gordon became an Olympic sailor.
Sources & photo credit
Biography and career ↗Biographical references ↗Additional biographical or achievement source ↗Original photograph. Cropped and displayed in monochrome.
Photo: Jiří Janíček. CC BY-SA 3.0 · Original image. Cropped and displayed in monochrome.