Science Fair Project Encyclopedia
Leonid Levin
Leonid Levin (born 1948, USSR) was a computer scientist and a student of Andrey Kolmogorov.
He emigrated to the USA in 1978.
He is well known for his work in randomness in computing, algorithmic complexity and intractability, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.
His life is described in a chapter in the book: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.
In 1973 he independently discovered a theorem which had been discovered and proven previously by Stephen Cook. The theorem, which is known as Cook or Cook-Levin theorem, was a breakthrough in computer science and is the foundation of computational complexity.
External links
09-23-2007 01:00:40
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details