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 ...
in
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 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 ...
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 ]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 ...
.
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 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.[Levin's curriculum vitae](_blank)
/ref> After researching algorithmic problems of information theory at the Moscow Institute of Information Transmission of the 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 ...
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 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 ...
in 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 ...
.
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 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 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 ...
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'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 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[ACM press release, August 22, 2012]
for his discovery of NP-completeness and the development of 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 ...
.
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