Leonid Levin

Leonid Anatolievich Levin (born November 2, 1948) is a Soviet-born American mathematician and computer scientist renowned for his pioneering work in computational complexity theory, including the independent formulation of the Cook-Levin theorem establishing the NP-completeness of the Boolean satisfiability problem in 1973 and the initiation of average-case complexity theory in 1984.

Born in Dnepropetrovsk, Ukraine (then part of the Soviet Union), Levin attended the Physics and Mathematics Boarding High School affiliated with Moscow State University, where he was introduced to advanced logic through lectures by Andrey Kolmogorov. He earned a master's degree from Moscow State University in 1970 and completed the requirements for a candidate of sciences degree (equivalent to a PhD) in 1972 under Kolmogorov's supervision, though the degree was not formally awarded at the time due to political circumstances in the Soviet Union. In 1978, Levin emigrated to the United States, where he joined the Massachusetts Institute of Technology and received his PhD in 1979 under advisor Albert R. Meyer.