Description
Co-discoverer of the Cook-Levin Theorem, Levin is noted for his work in randomness computing, algorithmic complexity, and intractability. This NP-completeness theorem was a basis for one of the seven "Millennium Math Problems" declared by the Clay Mathematics Institute with a $1,000,000 prize offered. It remains a breakthrough in computer science and 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.
Levin has served as a professor of computer science at Boston University, where he began teaching in 1980.
