- Leonid Levin
Leonid Anatolievich Levin ( _he. לאוניד אנטולייביץ לוין; _ru. Леонид Анатольевич Левин; born
November 2 ,1948 inDnipropetrovsk Ukrainian SSR ) is acomputer scientist. He studied underAndrey Kolmogorov .He obtained his master degree in 1970 and first
Ph.D . in 1972 atMoscow University . Later, he emigrated to the U.S. in 1978 and earned another Ph.D at theMassachusetts Institute of Technology in 1979.He is well known for his work in
randomness incomputing ,algorithmic complexity and intractability,average-case complexity [Leonid Levin. Average-case complete problems. SIAM J. Comput., 15:285–286, 1986] , foundations ofmathematics andcomputer science ,algorithmic probability ,theory of computation , andinformation theory .His life is described in a chapter of the book "Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists".cite book |title=Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists|first=Dennis|last=Shasha|coauthors=Cathy Lazere |year=1995|month=September|publisher=Springer|isbn=0-387-97992-1]
Levin independently discovered a theorem that was also discovered and proven by
Stephen Cook . This NP-completeness theorem, often called by inventors' names (seeCook-Levin Theorem ) was a basis for [http://www.claymath.org/millennium/P_vs_NP/ one of the seven "Millennium Math. Problems"] declared by Clay Mathematics Institute with a $1,000,000 prize offered. It was a breakthrough incomputer science and is the foundation ofcomputational 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 (see Trakhtenbrot's survey)cite journal|author=Boris A. Trakhtenbrot|title=A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms|url=http://csdl.computer.org/comp/mags/an/1984/04/a4384abs.htm|journal=Annals of the History of Computing|publisher=IEEE|volume=6|issue=4|pages=384–400|year=1984|doi=10.1109/MAHC.1984.10036] , 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.Notes
ee also
*
Cook-Levin theorem External links
* [http://www.cs.bu.edu/~lnd Levin's home page] at Boston University.
Persondata
NAME= Levin, Leonid Anatolievich
ALTERNATIVE NAMES=
SHORT DESCRIPTION=Russian-American computer scientist and mathematician
DATE OF BIRTH=1948
PLACE OF BIRTH=Dnipropetrovsk, Ukrainian SSR
DATE OF DEATH=
PLACE OF DEATH=
Wikimedia Foundation. 2010.
