Stephen Cook on Complexity Theory

Note: These resources are password protected.

The Importance of the P versus NP Question

A brief (3 page) discussion of why the question matters and what Cook thinks the answer is. From the Journal of the ACM 50 (2003): 27-29.

An Overview of Computational Complexity

Cook's 1982 Turing Award lecture. He gives a quick historical overview, then discusses fundamental issues involved in defining and proving complexity bounds on problems, talks about probabilistic and parallel algorithms, and concludes with speculations about the future of complexity theory. From Communications of the ACM 26 (1983): 401-408.

The Complexity of Theorem Proving Procedures

This is the foundational paper in which Cook proved that the satisfiability problem is NP-complete. From Proceedings of the Third Annual ACM Symposium on the Theory of Computing (1971): 151-158.

The P =? NP Poll

Guest Column: The P=?NP Poll

Bill Gasarch writes: “The P=?NP problem has been open since the early 1970's. When will it be solved? How will it be resolved? What techniques will be used? While it is impossible to answer these questions with any certainty, one can say for certain what one thinks may happen. We have taken a poll of theorists to see what they think. This is a report on that poll.” From ACM SIGACT News (June 2002): 34-47.

[ Return to the CPSCI 330 homepage ]