A.M. TURING AWARD WINNERS BY...

Stephen Arthur Cook

Canada – 1982
Additional Materials

Oral interview

A transcript of an oral interview of Stephen Cook was done for the Charles Babbage Institute by Philip L. Frana, 18 October 2002. In this interview Cook recounts his early interest in electronics and association with electronic cardiac pacemaker inventor Wilson Greatbatch, and his education at the University of Michigan and Harvard University. He describes his first position as an assistant professor of mathematics at the University of California, Berkeley, and his growing interest in problems of computational complexity preceding an influential 1971 presentation on “The Complexity of Theorem Proving Procedures” at the ACM SIGACT Symposium on the Theory of Computing. Cook discusses his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award for “contributions to the theory of computational complexity, including the concept of nondeterministic, polynomial-time completeness.” He also discusses the feasibility of solving the P versus NP Problem. The interview is available here.

 

P, NP and the Sudoku Puzzle
 

A simple example which elucidates the relationship between the classes P and NP is the popular Sudoku puzzle. In its most common form, a Sudoku puzzle is a 9-by-9 grid, comprised of nine 3-by-3 subgrids. Some of the entries of this grid are filled with numbers from 1 to 9 and others are left blank. The puzzle is solved by filling in the blank entries with numbers from 1 to 9 in such a way that each row, each column, and each subgrid contain all the numbers. Of course this means that in each of these groupings, there is no repetition. While it is straightforward to verify a solution to a puzzle, the popularity of the puzzle is due to the fact that in general, it may be very hard to find a solution. Here we have an example of a problem which is hard to solve, but has solutions which are easy to verify. It is not hard to see that we could consider Sudoku puzzles of arbitrary size. In this case we must fill an n-by-n grid using the numbers from 1 to n, subject to the same constraints we have in the standard puzzle. In this case, the problem of deciding whether or not a puzzle has a solution is NP-complete.