Stephen Cook facts for kids
Quick facts for kids
Stephen Cook
OC OOnt
|
|
|---|---|
Cook in 2008
|
|
| Born |
Stephen Arthur Cook
December 14, 1939 Buffalo, New York
|
| Alma mater | Harvard University University of Michigan |
| Known for | NP-completeness Propositional proof complexity Cook–Levin theorem |
| Awards |
|
| Scientific career | |
| Fields | Computer Science |
| Institutions | University of Toronto University of California, Berkeley |
| Thesis | On the Minimum Computation Time of Functions (1966) |
| Doctoral advisor | Hao Wang |
| Doctoral students | Mark Braverman Toniann Pitassi Walter Savitch Arvind Gupta Anna Lubiw |
Stephen Arthur Cook (born December 14, 1939) is a famous American-Canadian computer scientist and mathematician. He has made very important discoveries in how computers solve problems. He is known for his work in computational complexity theory, which studies how hard problems are for computers to solve. He also works on proof complexity, which looks at how long it takes to prove things in math.
Cook is now a professor emeritus at the University of Toronto. Many people see him as one of the main founders of computational complexity theory.
Contents
Life and Education
.jpg)
Stephen Cook started his journey in higher education at the University of Michigan. He earned his first degree, a bachelor's degree, in 1961. After that, he went to Harvard University. There, he earned his master's degree in 1962. He then completed his PhD in Mathematics in 1966.
After finishing his studies, Cook became a professor at the University of California, Berkeley. He taught mathematics there from 1966 to 1970. In 1970, he moved to Canada and joined the University of Toronto. He became an associate professor there. He was promoted to a full professor in 1975. Later, in 1985, he became a Distinguished Professor.
Understanding Computer Problems
Stephen Cook's research has greatly helped us understand how computers solve problems. He looked at how complex different tasks are for computers.
The Cook–Levin Theorem
In 1971, Cook wrote a very important paper. It was called "The Complexity of Theorem Proving Procedures." In this paper, he introduced two key ideas:
- Polynomial-time reduction: This is a way to show that one problem can be solved as easily as another. If you can solve problem A, you can use that solution to solve problem B quickly.
- NP-completeness: This describes a group of problems that are very hard for computers to solve quickly. Even if you can check an answer fast, finding the answer itself might take a very long time.
Cook proved that a problem called the Boolean satisfiability problem (often called SAT) is NP-complete. This means SAT is one of the hardest problems in this group. Another scientist, Leonid Levin, discovered the same thing around the same time. Because of this, it is now known as the Cook–Levin theorem.
The P vs. NP Problem
Cook's paper also introduced one of the biggest unsolved questions in computer science: the P vs. NP problem.
- P problems are those that computers can solve quickly.
- NP problems are those where, if someone gives you a possible answer, a computer can check if it's correct quickly. But finding the answer in the first place might be very hard.
The P vs. NP question asks: If a computer can check an answer quickly (NP), can it also find that answer quickly (P)?
Stephen Cook believes that P is not equal to NP. This means he thinks there are many problems where checking the answer is easy, but finding the answer is very hard. This question is so important that it is one of the seven Millennium Prize Problems. If someone solves it, they could win a million dollars!
Awards for His Work
In 1982, Stephen Cook received the Turing Award. This is one of the highest honors in computer science. He won it for his deep understanding of how complex computer problems are. The award recognized his paper on NP-completeness. This paper helped create a whole new area of study in computer science.
Other Contributions
Cook also worked on how to prove mathematical statements using computers. He helped create the field of proof complexity. This area studies how long and complicated proofs need to be. He also helped define important groups of problems, like NC and AC. The complexity class SC is even named after him!
Awards and Honors
Stephen Cook has received many awards for his important work.
- In 1977, he received the NSERC E.W.R. Steacie Memorial Fellowship.
- He won a Killam Research Fellowship in 1982.
- In 1999, he received the CRM-Fields-PIMS prize.
- He also won the John L. Synge Award and the Bernard Bolzano Medal in 2008.
- He is a member of the Royal Society of London and the Royal Society of Canada.
- He was chosen to be a member of the National Academy of Sciences in the United States. He is also a member of the American Academy of Arts and Sciences.
In 2008, the Association for Computing Machinery made him a Fellow. This was to honor his basic contributions to the theory of computational complexity. He also gave the Gödel Lecture in 1999.
The Government of Ontario gave him the Order of Ontario in 2013. This is the highest honor in Ontario, Canada. In 2012, he won the Gerhard Herzberg Canada Gold Medal for Science and Engineering. This is the top award for scientists and engineers in Canada. In 2015, he was named an Officer of the Order of Canada.
In 2015, Cook received the BBVA Foundation Frontiers of Knowledge Award. He won it for his key role in figuring out what computers can and cannot solve efficiently. His work has had a huge impact on many areas where complex computer tasks are important.
Stephen Cook has also guided many students. He has helped 36 students earn their PhD degrees.
Family Life
Stephen Cook lives in Toronto, Canada, with his wife. They have two sons. One of their sons, Gordon Cook, is an Olympic sailor.
See also
