[2] He joined the University of California, Berkeley, mathematics department in 1966 as an assistant professor, and stayed there until 1970 when he was denied reappointment.

In a speech celebrating the 30th anniversary of the Berkeley electrical engineering and computer sciences department, fellow Turing Award winner and Berkeley professor Richard Karp said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure.

Given the abundance of such optimization problems in everyday life, a positive answer to the "P vs. NP" question would likely have profound practical and philosophical consequences.

Cook conjectures that there are optimization problems (with easily checkable solutions) that cannot be solved by efficient algorithms, i.e., P is not equal to NP.

The ensuing 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 for the last decade.In his "Feasibly Constructive Proofs and the Propositional Calculus"[7] paper published in 1975, he introduced the equational theory PV (standing for Polynomial-time Verifiable) to formalize the notion of proofs using only polynomial-time concepts.

Cook co-authored a book with his student Phuong The Nguyen in this area titled "Logical Foundations of Proof Complexity".

[11] According to Don Knuth the KMP algorithm was inspired by Cook's automata for recognizing concatenated palindromes in linear time.

[17] The Herzberg Medal is awarded by NSERC for "both the sustained excellence and overall influence of research work conducted in Canada in the natural sciences or engineering".

[19] Cook was granted the BBVA Foundation Frontiers of Knowledge Award 2015 in the Information and Communication Technologies category "for his important role in identifying what computers can and cannot solve efficiently," in the words of the jury's citation.