U of T computer scientist receives international award for pushing frontiers of knowledge

Stephen Cook has won the prestigious BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category for his pioneering and influential work on computational complexity.  

A University Professor Emeritus, Cook said he is “astonished” and “delighted” by the award. In his long career, he has been fascinated to see how “computer science has advanced in leaps and bounds.” 

World-renowned research

• Cook expanded on Turing’s concept of computability – what a computer can and cannot solve – to include efficiency, so we can ascertain which problems are worth trying to solve and which are not 
• He defined a class of “hardest problems”, termed NP-complete, such that solving one efficiently would mean all other NP problems were similarly solvable. “If you can show that a problem is NP-complete, then very likely you should give up trying to solve it,” Cook said.
• Cook is author of one of the Millennium Problems; one, concretely, whose solution touches on the encryption and security systems underpinning the digital economy

“Steve’s contributions to research and teaching are exemplary, to say the least,” said Professor Ravin Balakrishnan, chair of the department of computer science. “His work has had global impact and the fundamental results of his decades of research continue to be at the absolute forefront of theoretical computer science.” 

Seminal Paper presented in 1971

Cook’s seminal paper on the complexity of theorem-proving procedures was presented in 1971, soon after he joined U of T’s newly created department of computer science.  

The paper had a tremendous impact on how scientists think about which problems can be computationally solved in a reasonable amount of time and Cook’s presentation has been described as one of those rare moments when the scientific world agrees the world has changed.  

His central achievement was to identify a sub-class of NP problems which he termed NP-complete, whose distinguishing features are, firstly, that they are the hardest and, secondly, that they are computationally equivalent: finding an efficient algorithm for one would yield algorithms for all the rest, and not just for the sub-set of NP-complete problems, but for NP problems as a whole.

“There are problems that a computer could feasibly solve, except that it would take until the sun burns out,” Cook said. “These are problems of the class we call NP. And then we have the class that we call P, which can be solved within an acceptable time frame. The trick is to decide which problems are NP [not efficiently solvable], and which are P [easily solvable].” 

Fundamental Problems in Computer Science

Cook has also 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 an A.M. Turing Award, 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.  

Cook received the NSERC Gerhard Herzberg Canada Gold Medal for Science and Engineering in 2012. He is an Officer to the Order of Canada, a fellow of the Royal Society of London and the Royal Society of Canada, and was awarded the Order of Ontario. Cook has also been elected to membership in the National Academy of Sciences (United States) and the American Academy of Arts and Sciences.

Acclaimed teacher

A very popular and effective teacher – currently teaching an undergraduate course on computational complexity and computability – Cook is also known as an excellent advisor and overall leader within the mathematical and computer science communities. 

(photo above courtesy NSERC)

The BBVA Frontiers of Knowledge Award recognizes those who push back the frontiers of the known world by posing radically innovative questions that have led to new knowledge and surprising possibilities.  Prizes are awarded annually in eight categories:     

• Basic Sciences
• Biomedicine
• Ecology & Conservation Biology
• Information & Communication Technologies
• Economics
• Finance and Management
• Contemporary Music
• Climate Change & Development Cooperation