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 Leonid Levin
Filter Results1 entry
Connections
Conjectures Posed
Published 1973 in the Soviet Union, independently of and roughly contemporaneously with Stephen Cook's 1971 formalization in the United States.
Source Clay Mathematics Institute
In Branch
Source Leonid Levin, Faculty Homepage, Boston University
Source Leonid Levin, Faculty Homepage, Boston University
Proofs Credited
Sources
1. Leonid Levin (Wikipedia)
Wikimedia Foundationopening paragraph
born November 2, 1948 ... in Dnipropetrovsk, Ukrainian SSR, Soviet Union.
Career section
He and Stephen Cook independently discovered the existence of NP-complete problems.
infobox pronunciation guide
LAY-oh-NEED LEV-in
Awards section
Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity.
View the Source 2. Clay Mathematics Institute
Clay Mathematics Institute
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.