Mathematician:Leonid Anatolievich Levin

Mathematician

Ukrainian-American computer scientist best known for his exposition of what is now known as the Cook-Levin Theorem.

Nationality

Ukrainian, now American

History

• Born: 2 Nov 1948, Dnipropetrovsk, USSR (now Ukraine)

Theorems and Definitions

• Cook-Levin Theorem (independently of Stephen Arthur Cook)

Results named for Leonid Anatolievich Levin can be found here.

Publications

• 1986: Average-case complete problems