Mathematicians
Leonid Levin
LAY-oh-NEED LEV-in
Also Known As Leonid Anatolievich Levin
Modern
Citation Formats
General Reference
APA Style
BibTeX
Professor in the Department of Computer Science at Boston University, working on computational complexity, randomness and holographic proofs. In 1973, working independently in the Soviet Union and unaware of Stephen Cook's 1971 result, Levin proved the same foundational fact of complexity theory in his paper Universal Search Problems, establishing NP-completeness by a different route; the shared result is now called the Cook-Levin theorem. He later emigrated to the United States and joined Boston University.
Facts
BirthplaceDnipropetrovsk, Ukrainian SSR, Soviet Union 1 Nationality / Culture Defining ContributionIndependently formalized NP-completeness in 1973 (Universal Search Problems), roughly contemporaneously with and unaware of Stephen Cook's 1971 work in the United States; jointly credited in the Cook-Levin theorem, the founding result underlying the P versus NP question. 2 Notable WorkIndependently co-discovered the existence of NP-complete problems with Stephen Cook (the Cook-Levin theorem). 1 AwardKnuth Prize (2012), for the discovery of NP-completeness and the development of average-case complexity; member, U.S. National Academy of Sciences. 1 Cross-Tradition Connections
Conjectures Posed
Published 1973 in the Soviet Union, independently of and roughly contemporaneously with Stephen Cook's 1971 formalization in the United States.
In Branch
Sources
Reader Challenges (0 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.