# Mathematician:Stephen Arthur Cook

Jump to navigation
Jump to search

American mathematician and computer scientist who has made considerable progress in the field of complexity theory.

## Nationality

American

## History

- Born: 14 Dec 1939, Buffalo, New York, USA
- 1961: Bachelor's degree from University of Michigan
- 1962: Master's degree from Harvard University
- 1966: Ph.D. from Harvard University
- 1966 - 1970: Assistant Professor at University of California, Berkeley
- 1970: Denied reappointment at Berkeley, joined University of Toronto as Associate Professor in the Computer Science and Mathematics departments
- 1975: Promoted to Professor
- 1977: Awarded a Steacie Fellowship
- 1982: Received the Turing award
- 1982: Awarded a Killam Research Fellowship
- 1985: Promoted to University Professor
- 1999: Received the CRM-Fields-PIMS prize

## Theorems and Definitions

- Cook-Levin Theorem (independently of Leonid Anatolievich Levin)
- Cook Reduction

Results named for **Stephen Arthur Cook** can be found here.

## Books and Papers

- 1971:
*The Complexity of Theorem Proving Procedures*(in which P versus NP was first formulated) - 1975:
*Feasibly Constructive Proofs and the Propositional Calculus* - 1979:
*The Relative Efficiency of Propositional Proof Systems*(with Robert A. Reckhow)

*Logical Foundations of Proof Complexity*(with Phuong The Nguyen)