Anatolievich Levin (Hebrew: לאוניד אנטולייביץ לוין; Russian: Леонид
Анатольевич Левин; born November 2, 1948 in Dnipropetrovsk Ukrainian
SSR) is a computer scientist. He studied under Andrey Kolmogorov.
He obtained his master degree in 1970 and first Ph.D. in 1972 at
Moscow University. Later, he emigrated to the U.S. in 1978 and earned
another Ph.D at the Massachusetts Institute of Technology in 1979.
He is well known for his work in randomness in computing, algorithmic
complexity and intractability, foundations of mathematics and computer
science, algorithmic probability, theory of computation, and
His life is described in a chapter of the book Out of Their Minds: The
Lives and Discoveries of 15 Great Computer Scientists.
Levin independently discovered a theorem that was also discovered and
proven by Stephen Cook. This NP-completeness theorem, often called by
inventors' names (see Cook-Levin Theorem) was a basis for one of the
seven "Millennium Math. Problems" declared by Clay Mathematics
Institute with a $1,000,000 prize offered. It was a breakthrough in
computer science and is the foundation of computational complexity.
Levin's journal article on this theorem was published in 1973; he had
lectured on the ideas in it for some years before that time (see
Trakhtenbrot's survey), though complete formal writing of the
results took place after Cook's publication.
He is currently a professor of computer science at Boston University,
where he began teaching in 1980.