Stephen Arthur Cook

1939-

American Mathematician

Stephen Cook, an American mathematician who teaches at the University of Toronto in Canada, is a specialist in computational complexity. In 1971 he advanced the theory of NP completeness, which addresses the solvability of certain problems.

Cook was born in Buffalo, New York, on December 14, 1939. His family later moved to Clarence, New York, where he met Wilson Greatbach (1919- ), inventor of the implantable pacemaker. Greatbach became the young man's mentor, and influenced him toward a career in electrical engineering. Cook duly enrolled in the science engineering program at the University of Michigan in 1957, but after taking a course in computer programming, he switched his major to mathematics.

After graduating from Michigan with a B.S. in mathematics in 1961, Cook went on to Harvard University, where he became interested in propositional calculus and complexity theory. He earned his M.S. from Harvard in 1962, and his Ph.D. in 1966. He then took a position as assistant professor of mathematics and computer science at the University of California, Berkeley, where he remained until 1970, when he joined the faculty of the University of Toronto.

In 1971 Cook presented a paper entitled "The Complexity of Theorem Proving Procedures," which introduced the theory of NP completeness. Computation complexity classifies problems by difficulty: P for problems that can be solved in polynomial time; NP for problems that can be solved in nondeterministic polynomial time (that is, a problem for which a solution can be guessed and tested in an undefined period of time); and so on. NP completeness addresses the distinction between P and NP.

Cook was promoted to professor in 1975, and in 1977 received a Steacie Fellowship. In 1982 he won the Alan M. Turing Award for his work on NP completeness, and received a Killam Research Fellowship. Promoted to university professor in 1985, he received Computer Science Teaching awards in 1989 and 1995. He is a fellow of the Royal Society of Canada, and was elected to membership in the (U.S.) National Academy of Sciences and the American Academy of Arts and Sciences.

Married in 1968, Cook has two children. He continues to pursue research in computational complexity, as well as programming language semantics, parallel computation, and the relationship between logic and complexity theory.

JUDSON KNIGHT