Stephen Cook

Stephen Cook is a Canadian-American computer scientist whose work established key foundations of computational complexity, especially the theory of NP-completeness and the Cook–Levin theorem.

Cook–Levin theorem: The theorem that Boolean satisfiability is NP-complete, proved by reducing every problem in NP to it. Cook’s 1971 result established the first NP-complete problem.
Polynomial-time reduction: A transformation between computational problems that can be computed in time bounded by a polynomial in input size. Cook used reductions to show that every NP problem can be represented by satisfiability.
Leonid Levin: A Soviet-American mathematician and computer scientist who independently established foundational results on NP-completeness. Levin independently proved a closely related completeness theorem in 1973.
University of Toronto: A public research university in Toronto, Canada, founded in 1827. Cook earned his undergraduate degree there before pursuing graduate study in the United States.
NP-completeness: A class of decision problems in NP to which every NP problem can be reduced in polynomial time. Cook introduced this framework through his theorem, making it central to complexity theory.
Boolean satisfiability problem: The decision problem of whether a Boolean formula has an assignment of truth values that makes it true. This is the specific problem Cook proved NP-complete.
Richard Karp: An American computer scientist known for algorithms, combinatorial optimization, and identifying 21 NP-complete problems. Karp demonstrated the breadth of Cook’s framework by proving many familiar problems NP-complete.
Harvard University: A private research university in Cambridge, Massachusetts, founded in 1636. Cook completed his doctorate in mathematics at Harvard in 1966.
P versus NP problem: The open question of whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. Cook’s work supplied the first concrete foundation for studying this central unresolved question.
NP (complexity class): The class of decision problems whose yes-instances have certificates verifiable in polynomial time. Cook’s theorem characterizes satisfiability as hard for every problem in this class.

Linked from 7 pages