# Stephen Cook

> American-Canadian computer scientist

**Wikidata**: [Q62870](https://www.wikidata.org/wiki/Q62870)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Stephen_Cook)  
**Source**: https://4ort.xyz/entity/stephen-cook

## Summary  
Stephen Arthur Cook is an American‑Canadian computer scientist best known for establishing the concept of NP‑completeness (Cook’s theorem) and for receiving the 1982 Turing Award for his fundamental contributions to computational complexity theory.

## Biography  
- **Born:** 14 December 1939, Buffalo, United States  
- **Nationality:** United States; Canada  
- **Education:**  
  - Harvard University (undergraduate)  
  - University of Michigan (Doctor of Sciences, doctoral advisor Hao Wang)  
- **Known for:** Introducing NP‑completeness and proving the Boolean satisfiability problem is NP‑complete (Cook’s theorem)  
- **Employer(s):** University of Toronto (current), University of California, Berkeley (past)  
- **Field(s):** Computer science, computational complexity  

## Contributions  
Stephen Cook’s most celebrated contribution is the 1971 proof that the Boolean satisfiability problem (SAT) is NP‑complete, now called **Cook’s theorem**. This work created the class **NP‑complete**, providing a framework for comparing the difficulty of decision problems and launching the modern theory of computational complexity. The theorem appeared in his seminal paper *“The Complexity of Theorem‑Proving Procedures”* (1971) and laid the groundwork for the subsequent **Cook–Levin theorem**, which formalized NP‑completeness for a broad class of problems. Cook’s research also includes influential papers on proof complexity, circuit complexity, and the foundations of cryptographic hardness. As a mentor, he supervised a generation of prominent computer scientists, including Toniann Pitassi, Anna Lubiw, Mark Braverman, and Walter Savitch. His work has been cited thousands of times and continues to shape algorithm design, cryptography, and theoretical computer science curricula worldwide.

## FAQs  
### Q: What is Stephen Cook most famous for?  
A: He proved that the Boolean satisfiability problem is NP‑complete (Cook’s theorem), establishing the concept of NP‑completeness in computational complexity theory.  

### Q: Which major awards has Stephen Cook received?  
A: He received the 1982 **Turing Award**, was elected a Fellow of the Royal Society (1998), a Fellow of the Royal Society of Canada (1984), an ACM Fellow (2009), and was appointed an Officer of the Order of Canada (2015), among other honors.  

### Q: Is Stephen Cook American or Canadian?  
A: He holds dual citizenship—both United States and Canada.  

### Q: Where does Stephen Cook work?  
A: He is a professor at the **University of Toronto** and previously held a faculty position at the **University of California, Berkeley**.  

### Q: Who are some of Stephen Cook’s notable doctoral students?  
A: His former students include Toniann Pitassi, Anna Lubiw, Mark Braverman, Walter Savitch, and Arvind Gupta, all of whom have become leading researchers in computer science.

## Why They Matter  
Cook’s theorem transformed the way computer scientists understand problem difficulty. By defining NP‑completeness, he gave a rigorous method to show that many practical problems are unlikely to have efficient (polynomial‑time) algorithms unless P = NP. This insight drives research in approximation algorithms, cryptography, and algorithmic lower bounds. The concept has become a cornerstone of theoretical computer science curricula and informs real‑world decisions in optimization, security, and software engineering. Without Cook’s breakthrough, the systematic study of computational hardness would lack its unifying framework, and many subsequent advances in complexity theory would not have a common foundation.

## Notable For  
- **Cook’s theorem (1971):** First proof that SAT is NP‑complete.  
- **1982 Turing Award:** Recognized for fundamental contributions to computational complexity.  
- **Fellow of the Royal Society (1998) and Royal Society of Canada (1984).**  
- **Officer of the Order of Canada (2015)** and **Gerhard Herzberg Canada Gold Medal (2012).**  
- Mentoring a generation of leading computer scientists, including Toniann Pitassi and Walter Savitch.

## Body  

### Early Life and Education  
- Born in Buffalo, New York, on 14 December 1939.  
- Completed undergraduate studies at **Harvard University**.  
- Earned a Doctor of Sciences from the **University of Michigan**, where **Hao Wang** served as his doctoral advisor.

### Academic Career  
- Joined the faculty of the **University of California, Berkeley**, where he began his work on computational complexity.  
- Later moved to the **University of Toronto**, where he holds a professorship and continues research and teaching.  

### Major Contributions  

#### Cook’s Theorem (1971)  
- Published *“The Complexity of Theorem‑Proving Procedures”* establishing SAT as NP‑complete.  
- Introduced the notion of **NP‑completeness**, enabling systematic classification of decision problems.  

#### Influence on Complexity Theory  
- Extended results to circuit complexity and proof complexity.  
- Provided foundational tools for later work on the **P vs NP** question.  

#### Mentorship  
- Supervised doctoral students who became prominent researchers:  
  - **Toniann Pitassi** (complexity and algorithms)  
  - **Anna Lubiw** (graph algorithms)  
  - **Mark Braverman** (probabilistic algorithms)  
  - **Walter Savitch** (space‑bounded computation)  
  - **Arvind Gupta** (theoretical computer science leadership)  

### Honors and Awards  
- **Turing Award (1982)** – ACM’s highest honor for contributions to computing.  
- **Fellow of the Royal Society (1998)** and **Royal Society of Canada (1984)**.  
- **ACM Fellow (2009)** – “For fundamental contributions to the theory of computational complexity.”  
- **Gerhard Herzberg Canada Gold Medal (2012)** – Canada’s top scientific award.  
- **Officer of the Order of Canada (2015)** – Recognizing national and international impact.  

### Legacy  
- Cook’s work underpins modern cryptographic assumptions, optimization theory, and algorithmic research.  
- His concepts are taught in virtually every computer‑science program worldwide.  
- The NP‑completeness framework continues to guide researchers in identifying tractable versus intractable problems.

## Schema Markup  
```json
{
  "@context": "https://schema.org",
  "@type": "Person",
  "name": "Stephen Arthur Cook",
  "jobTitle": "Computer scientist",
  "worksFor": {
    "@type": "Organization",
    "name": "University of Toronto"
  },
  "nationality": {
    "@type": "Country",
    "name": "United States"
  },
  "birthDate": "1939-12-14",
  "birthPlace": "Buffalo, United States",
  "alumniOf": [
    {
      "@type": "EducationalOrganization",
      "name": "Harvard University"
    },
    {
      "@type": "EducationalOrganization",
      "name": "University of Michigan"
    }
  ],
  "knowsAbout": [
    "Computer science",
    "Computational complexity"
  ],
  "sameAs": [
    "https://en.wikipedia.org/wiki/Stephen_Cook"
  ],
  "description": "Stephen Arthur Cook is an American‑Canadian computer scientist renowned for proving the NP‑completeness of the Boolean satisfiability problem and receiving the 1982 Turing Award."
}

## References

1. Integrated Authority File
2. [Source](https://amturing.acm.org/award_winners/cook_n991950.cfm)
3. [Source](https://awards.acm.org/award_winners/cook_N991950#140)
4. [Source](https://awards.acm.org/award_winners/cook_N991950#158)
5. [Source](https://www.acm.org/media-center/2009/january/acm-names-44-fellows-for-contributions-to-computing-and-it)
6. [Source](https://rsc-src.ca/en/awards-excellence/past-award-winners)
7. Mathematics Genealogy Project
8. International Standard Name Identifier
9. Virtual International Authority File
10. Freebase Data Dumps. 2013
11. IdRef
12. Quora