Leonid Levin

Leonid Levin (born November 2, 1948, in Dnipropetrovsk, Ukrainian SSR, Soviet Union) is a Soviet-American mathematician and computer scientist who has taught computer science at Boston University since 1980. His research addresses randomness in computing, algorithmic complexity, average-case complexity and information theory. Levin and Stephen Cook independently discovered the existence of NP-complete problems, a result known as the Cook-Levin theorem that became foundational to computational complexity theory. He received the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity, and is a member of the United States National Academy of Sciences and a Fellow of the American Academy of Arts and Sciences.