2005 NSERC Award of Excellence

Stephen Cook

The security of every e-commerce transaction depends on a silicon irony: the secrecy of your credit card information relies not on what computers *can do*, but on what they *cannot*. It is an oddity that stands as one of the great mathematical mysteries of the 21st century. For the past 35 years, no one has shed more light on this, and other limitations of computation, than Dr. Stephen Cook. He is one of three nominees in 2005 for the prestigious Gerhard Herzberg Canada Gold Medal for Science and Engineering.

Public attention is understandably focused on the amazing things computers enable us to do, from searching the Internet to computational weather forecasting. However in outlining the first mathematical model for his Turing Machine in 1936, Alan Turing (a pioneer of computer science) noted that even then there were some kinds of mathematical problems that his machine would not be able to solve.

The possibility of limitation surfaced again with the rapid rise in computing after World War II. Scientists often found themselves unable to develop efficient algorithms, or methods of doing a computation, for particular problems they were trying to solve. Was this because the scientists needed to work harder, or were they banging their heads against a mainframe that would never provide an answer? It became the question at the heart of a new discipline in computer science that revolved around complexity theory – a theoretical field that tries to explain the natural variability in the difficulty of computational problems.

It was into this early realm of computer science thinking that a teenaged Stephen Cook began his math studies at the University of Michigan in the late 1950s. As an undergraduate, he worked with his first computer, a vacuum-tube Bendix G15 at the Cornell Aeronautical Laboratory in Buffalo, New York, part of a research project to develop an automated aircraft carrier landing system. Notably, it is a complex problem that almost 50 years later is still not automated. The immensity of the challenge profoundly shaped Cook's imagination and thinking.

"The 1960s computers were relatively new and one of the key questions was what is the intrinsic computational difficulty of complicated problems," says Dr. Cook from his office at the University of Toronto.

As a Harvard doctoral student, Dr. Cook cut his intellectual teeth on complexity theory by proving the computational limitations on the precise multiplication of large numbers.

After graduation, he landed a job as an assistant mathematics professor at the University of California, Berkeley, working at the interface of mathematics and computer science. When denied tenure in the math department, Dr. Cook accepted a position at what he recalls as the vibrant and young computer science department in Toronto.

Soon after arriving there in 1970, Dr. Cook made the seminal insights that changed the way scientists think about which problems can be computationally solved in a reasonable amount of time. At a symposium in the United States on the theory of computing in 1971, Dr. Cook presented a brief paper entitled "The Complexity of Theorem Proving Procedures." It was one of those rare, elegant moments at which there is instant peer recognition that the scientific world has changed. Dr. Cook showed how to identify a large class of problems, known as NP-complete problems, that apparently cannot be efficiently solved by computation.

Many of these NP-complete problems involve queuing and scheduling, a major challenge in many businesses (e.g., courier companies trying to maximize route efficiency). NP-complete problems are characterized by the fact that if given the answer you would be able to quickly verify its correctness, but getting that answer is computationally impractical.

For example, imagine you're organizing housing for 400 university students, but there's only dorm space for 100. Additionally, the dorm master has identified pairs of incompatible students. In this case, if someone gives you a final list, it's easy to check if there are pairs of incompatible students. But the task of choosing the 100 students is so hard it's computationally impractical – the number of possible ways of choosing the 100 students is greater than the number of atoms in the universe. In other words, it's not that the computer would not finally spit out an answer, just that you would not be around to read it.

Cook's Theorem, as it became known, offered a way of classifying computational problems into efficiently solvable ones and those that are NP-complete. Since then, thousands of scientific problems have been identified as NP-complete. Realizing that it's impractical to find complete answers to these questions has driven researchers to develop innovative computational techniques to determine approximate answers.

For now the secrecy of information on the Internet is based on the assumption that even with the world's fastest supercomputer no one could efficiently break the encrypted code in a reasonable amount of time.

The quest to find a rigorous mathematical proof (or disproof) of this assumption is the famous P versus NP problem, one of the Clay Mathematics Institute's famous Millennium Prize Problems that has a prize fund of $1 million for the solution.

"Anyone who comes up with an algorithm that efficiently solves an NP-complete problem wins the million dollars," says Dr. Cook. "But, the real problem is that I don't think there is any algorithm. The real challenge is to prove the non-existence of such an algorithm."

**Accomplishments**

Dr. Cook is the only person in Canada to have won the Association for Computing Machinery’s A.M. Turing Award, computer science's most prestigious prize. From Dr. Cook’s 1982 citation notes: *For his advancement of our understanding of the complexity of computation in a significant and profound way. The exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science. *

While actively pursuing research for four decades, Dr. Cook has been a dedicated mentor and teacher. He received various University of Toronto computer science teaching awards in 1989 and 1995. Twenty-five students have completed their Ph.D. degrees under his supervision. His first student, Dr. Walter Savitch, was made famous by "Savitch's Theorem," and recently retired after a long teaching career at the University of California, San Diego. More recently, Toniann Pitassi received her Ph.D. in 1992, won the National Science Foundation (United States) Young Investigator Award, and later returned to Canada with an NSERC University Faculty Award. Dr. Pitassi is now Dr. Cook's colleague as a professor at the University of Toronto.

Dr. Cook was awarded an E.W.R. Steacie Memorial Fellowship from NSERC in 1977 and a Killam Research Fellowship in 1982. He is a fellow of the Royal Society of Canada, the Royal Society of London, and was elected to membership in the National Academy of Sciences (United States), and the American Academy of Arts and Sciences.

**Biographical Overview**

Dr. Stephen Arthur Cook was born in Buffalo, New York in 1939. He received his B.Sc. degree from the University of Michigan in 1961, and his S.M. and Ph.D. degrees from Harvard University in 1962 and 1966, respectively. From 1966 to 1970 he was Assistant Professor, University of California, Berkeley. He joined the faculty at the University of Toronto in 1970 as an Associate Professor, and was promoted to Professor in 1975, and University Professor in 1985.