Leonid Anatolievich Levin ( ; russian: Леони́д Анато́льевич Ле́вин; uk, Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

. He is known for his work in

randomness In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...

computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...

algorithmic complexity Algorithmic may refer to: *Algorithm, step-by-step instructions for a calculation **Algorithmic art, art made by an algorithm **Algorithmic composition, music made by an algorithm ** Algorithmic trading, trading decisions made by an algorithm **Alg ...

and intractability,

average-case complexity In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case comp ...

, foundations of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

algorithmic probability In algorithmic information theory, algorithmic probability, also known as Solomonoff probability, is a mathematical method of assigning a prior probability to a given observation. It was invented by Ray Solomonoff in the 1960s. It is used in induc ...

theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., a ...

, and

information theory Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...

. He obtained his master's degree at

Moscow University M. V. Lomonosov Moscow State University (MSU; russian: Московский государственный университет имени М. В. Ломоносова) is a public research university in Moscow, Russia and the most prestigious ...

in 1970 where he studied under

Andrey Kolmogorov Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...

and completed the

Candidate Degree Candidate of Philosophy can refer to the US degree or status of Candidate in Philosophy (C.Phil. or Ph.C.) granted to Ph.D. students who have been accepted as candidates for that degree, or (as a direct translation) to degrees or former degrees at ...

academic requirements in 1972. He and

Stephen Cook Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor at the Unive ...

independently discovered the existence of

NP-complete problems In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

. This NP-completeness theorem, often called the

Cook–Levin theorem In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a determi ...

, was a basis for one of the seven

Millennium Prize Problems The Millennium Prize Problems are seven well-known complex mathematical problems selected by the Clay Mathematics Institute in 2000. The Clay Institute has pledged a US$1 million prize for the first correct solution to each problem. According ...

declared by the

Clay Mathematics Institute The Clay Mathematics Institute (CMI) is a private, non-profit foundation (nonprofit), foundation dedicated to increasing and disseminating mathematics, mathematical knowledge. Formerly based in Peterborough, New Hampshire, the corporate address i ...

with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in

and an important step in the development of the theory of

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

. Levin was awarded the

Knuth Prize The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth. History The Knuth Prize has been awarded since 1996 and includes an award of US ...

in 2012 for his discovery of NP-completeness and the development of

. He is a member of the US

National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nati ...

and a fellow of the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (abbreviation: AAA&S) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and ...

Biography

He obtained his master's degree at

in 1970 where he studied under

and completed the

academic requirements in 1972.Levin's curriculum vitae
/ref> After researching algorithmic problems of information theory at the Moscow Institute of Information Transmission of the

in 1972–1973, and a position as Senior Research Scientist at the Moscow National Research Institute of Integrated Automation for the Oil/Gas Industry in 1973–1977, he emigrated to the

U.S. The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territori ...

in 1978 and also earned a Ph.D. at the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...

(MIT) in 1979. His advisor at MIT was

Albert R. Meyer Albert Ronald da Silva Meyer (born 1941) is Hitachi America Professor emeritus of computer science at Massachusetts Institute of Technology (MIT). Biography Meyer received his PhD from Harvard University in 1972 in applied mathematics, under t ...

. He is well known for his work in

and intractability,

, foundations of

and

, and

. His life is described in a chapter of the book ''Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists''. Levin and

independently discovered the existence of

. This NP-completeness theorem, often called the

, was a basis for one of the seven

declared by the

with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in

and an important step in the development of the theory of

. Levin's journal article on this theorem was published in 1973;(pdf)
/ref> he had lectured on the ideas in it for some years before that time (see Trakhtenbrot's survey), though complete formal writing of the results took place after Cook's publication. Levin was awarded the

in 2012ACM press release, August 22, 2012
for his discovery of NP-completeness and the development of

. He is currently a professor of computer science at

Boston University Boston University (BU) is a private research university in Boston, Massachusetts. The university is nonsectarian, but has a historical affiliation with the United Methodist Church. It was founded in 1839 by Methodists with its original campu ...

, where he began teaching in 1980.

Notes

References

External links

Levin's home page
at Boston University.

{{DEFAULTSORT:Levin, Leonid 1948 births Living people Scientists from Dnipro Massachusetts Institute of Technology alumni Moscow State University alumni American computer scientists American people of Ukrainian-Jewish descent 20th-century American mathematicians 21st-century American mathematicians Boston University faculty Russian information theorists Russian computer scientists Russian mathematicians Soviet computer scientists Soviet mathematicians Soviet emigrants to the United States American information theorists 21st-century Russian politicians Knuth Prize laureates Ukrainian mathematicians Ukrainian Jews