Leonid Anatolievich Levin

Levin independently discovered a theorem also proven by Stephen Cook. This NP-completeness theorem, often called the Cook-Levin Theorem, was a basis for one of the seven "Millennium Math. Problems" declared by Clay Mathematics Institute with a $1,000,000 prize offered. It was a breakthrough in computer science and is the foundation of computational complexity. Levin's journal article on this theorem was published in 1973; he had lectured on the ideas in it for some years before that time, though complete formal writing of the results took place after Cook's publication. He is currently a professor of computer science at Boston University, where he began teaching in 1980.