• 1948 November 02
    (b.) - ?


Levin independently discovered a theorem also proven by Stephen Cook. This NP-completeness theorem, often called the Cook-Levin Theorem, was a basis for one of the seven "Millennium Math. Problems" declared by Clay Mathematics Institute with a $1,000,000 prize offered. It was a breakthrough in computer science and is the foundation of computational 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, 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.
  • Date of Birth:

    1948 November 02
  • Gender:

  • Noted For:

    Noted for his work in randomness computing, algorithmic complexity and intractability
  • Category of Achievement:

  • More Info: