# Leonid Levin

Updated: 09/15/2017 by Computer Hope

**Name:** Leonid Anatolievich Levin

**Born:** November 2, 1948, in Dnipropetrovsk, Ukrainian SSR, Soviet Union

## Computer-related contributions

- Soviet-American computer scientist.
- Known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.
- 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.

## Significant publications

- Randomness and non-determinism (1992).
- Average case complete problems; One-way functions and pseudorandom generators; Computational complexity of functions (1985).

## Honors and awards

- Awarded the Knuth Prize (2012).