Leonid Anatolievich Levin (le-oh-NEED LE-vin; Russian: Леони́д Анато́льевич Ле́вин; Ukrainian: Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist.


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.[1][2] After researching in algorithmic problems of information theory at the Moscow Institute of Information Transmission of the National Academy of Sciences in 1972-1973, and a position as Senior Research Scientist at the Moscow National Research Institute of Integrated Automation for the Oil/Gas Industry in 1973-1977, he emigrated to the U.S. in 1978 and also earned a Ph.D. at the Massachusetts Institute of Technology (MIT) in 1979.[1] His advisor at MIT was Albert R. Meyer.

He is well known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity,[3] foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.

His life is described in a chapter of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.[4]

Levin 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's journal article on this theorem was published in 1973;[5] he had lectured on the ideas in it for some years before that time (see Trakhtenbrot's survey),[6] though complete formal writing of the results took place after Cook's publication.

Levin was awarded the Knuth Prize in 2012[7] for his discovery of NP-completeness and the development of average-case complexity.

He is currently a professor of computer science at Boston University, where he began teaching in 1980.


  1. ^ a b Levin's curriculum vitae
  2. ^ 1971 Dissertation (in Russian); English translation at arXiv
  3. ^ Levin, Leonid (1986). "Average-case complete problems". SIAM J. Comput. 15 (1): 285–6. doi:10.1137/0215020. 
  4. ^ Shasha, Dennis; Cathy Lazere (September 1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Springer. ISBN 0-387-97992-1. 
  5. ^ Levin, Leonid (1973). "Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii) 9 (3): 115–116.  (pdf)
  6. ^ Boris A. Trakhtenbrot (1984). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". Annals of the History of Computing[dead link] (IEEE) 6 (4): 384–400. doi:10.1109/MAHC.1984.10036. 
  7. ^ ACM press release, August 22, 2012


External links