�山ǿ��

Stephen Cook is among a short list of mathematics researchers whose ideas have spawned new fields of inquiry for current and future generations —and he teaches both undergraduate and graduate students at the University of Toronto.

A professor of and mathematics, Cook is the 2012 winner of the Natural Sciences and Engineering Research Council’s Herzberg Medal.

Cook’s 1971 paper “The complexity of theorem–proving procedures” gave mathematical meaning to “efficiently computable” and “efficiently provable.” He identified a large class of important problems that appear to be computationally intractable, but a tractable algorithm for any one of them would yield tractable algorithms for all of them.

He received an A.M. Turing Award for his work, the highest honour for a researcher in computer science, and his inquiries are now among the essential theoretical results that all computer science graduates must understand. The basic question he raised is now among the seven Millennium Prize Problems in mathematics, solutions to which are each worth US$1 million.

In addition to celebrated contributions to complexity theory, Cook has made fundamental contributions to computational theory, algorithm design, programming languages and mathematical logic, and his still-growing body of work is likely to be cited for many decades to come. He received the CRM/Fields Institute Prize in 1999, is a fellow of the Royal Society of London and 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. Last month, he was awarded the Order of Ontario.

�山ǿ�� News asked Cook to discuss his work and its implications for future generations.

Tell us about your research.
My field is the study of the computational difficulty of problems solvable by computers. My name is associated with the so-called P versus NP question, which is one of the seven Millennium Prize problems listed by the Clay Mathematics Institute in the year 2000. To answer this question, one must prove or disprove that a large and important class of problems would require billions of years to solve by any computer of the kind we currently envision. This is important partly because cryptographic protocols such as the RSA public key encryption scheme depend for their security upon currently unproven assumptions about what computers cannot do.

What kind of impact could this research have for society?
This work has had, and will continue to have, two kinds of impact. The first kind is mentioned above: It helps in the development of secure cryptographic systems. The second kind concerns the development of efficient computer algorithms.  A major goal of my field is to sort out which kinds of computer problems can be solved efficiently, and which are intractable. Impossibility proofs can help in constructing useful algorithms in the same way that the conservation of energy principle helps in the design of machines: Don't waste your time trying to build a perpetual motion machine.

What sort of changes/developments have you witnessed over the course of your career?
Computers were a curiosity when I was a graduate student in the 1960s, and now they are an important part of our lives. In the meantime we have learned a great deal about what can and cannot be computed efficiently, but as computers become more pervasive the questions become more important.

What drew you to this field – and to this particular focus?
I enrolled as a mathematics graduate student at Harvard in 1961, thinking I'd concentrate in algebra. Computer Science did not yet exist as a discipline. After taking a course in `logic and computation' from Hao Wang, my future advisor, I switched fields. My PhD thesis was inspired by a question posed by a pioneer in the field named Alan Cobham: Is multiplication (of large numbers) intrinsically harder than addition? Part of the challenge was to formulate this as a precise mathematical question.

Why �山ǿ��?
I joined the faculty of the computer science department at �山ǿ�� in 1970. This was one of the world's first CS departments, and Tom Hull, the department chair, had a powerful vision for its future. He already had recruited some aspiring young faculty, including my close colleague Allan Borodin, who continues to be a pillar of the department. It helped that Toronto is a good sailing venue on Lake Ontario, and sailing was (and is) a major hobby for my wife and me.

What advice would you give to a student just starting out in this field?
You've made a good choice. The possibilities are boundless.