Lesson plan

Leonid Levin

Leonid Anatolievich Levin ( ; ; ; born November 2, 1948) is a Soviet-American mathematician and computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. He obtained his master's degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972. He and Stephen Cook independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook–Levin theorem, was a basis for one of the seven Millennium Prize Problems declared by the Clay Mathematics Institute with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in computer science and an important step in the development of the theory of computational complexity. Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity. He is a member of the US National Academy of Sciences and a fellow of the American Academy of Arts and Sciences.

Back to article

Article summary

Leonid Anatolievich Levin ( ; ; ; born November 2, 1948) is a Soviet-American mathematician and computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. He obtained his master's degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972. He and Stephen Cook independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook–Levin theorem, was a basis for one of the seven Millennium Prize Problems declared by the Clay Mathematics Institute with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in computer science and an important step in the development of the theory of computational complexity. Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity. He is a member of the US National Academy of Sciences and a fellow of the American Academy of Arts and Sciences.

Key claims

  1. date of birth: 1948-11-02 — source: Wikipedia, revision 1371962154, retrieved 2026-10-20 · confidence 0.95
  2. publication date: 1973 — source: Wikipedia, revision 1371962154, retrieved 2026-10-20 · confidence 0.95

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. The record states that the date of birth is "1948-11-02". What evidence would count against this claim?
  3. The record states that the publication date is "1973". What evidence would count against this claim?
  4. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  5. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

  1. Wikipedia, “Leonid Levin”, revision 1371962154, retrieved 2026-10-20 https://en.wikipedia.org/w/index.php?oldid=1371962154

Key claims and bibliography are generated from the same tracked claims and sources as the article page.