Abstract: We present an historical overview of
computational complexity theory. The emphasis is on the importance,
plausibility and difficulty of the conjecture that P is not equal
to NP, which Steve Smale listed as one of the top three mathematical
problems for the next century.
Stephen
Cook was born in Buffalo, New York.
He received his BSc degree from the University of Michigan in 1961
and his SM and PhD degrees from Harvard University in 1962 and 1966
respectively.
From 1966 to 1970 he was an Assistant Professor at the University
of California, Berkeley. He joined the University of Toronto in 1970
as an Associate Professor and was promoted to a Professor in 1975.
Dr. Cook's principal research area is computational complexity, with
excursions into programming language semantics, parallel computation
and especially the interaction between login and complexity theory.
He has authored over 50 research papers, including his famous 1971
paper, "The Complexity of Theorem Proving Procedures," which introduced
the theory of NP completeness.
Dr. Cook was the 1982 recipient of the Turing award, and was awarded
a Steacie Fellowship in 1977 and a Killam Research Fellowship in 1982.
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 National Academy of Sciences (United States) and the American
Academy of Arts and Sciences.
