page_title: Leonid Levin
hierarchical_section_title: Leonid Levin
caption_attribution_description: English: Leonid Levin before giving a talk at Rutgers University in 2010.
context_page_description: Leonid Anatolievich Levin is a Soviet-American computer scientist.
  He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. He obtained his master's degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972.
  He and Stephen Cook independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook–Levin theorem, was a basis for one of the seven Millennium Prize Problems declared by the Clay Mathematics Institute with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in computer science and an important step in the development of the theory of computational complexity.
  Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity. His life is described in a chapter of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.
context_section_description: Leonid Anatolievich Levin (/leɪ.oʊˈniːd ˈlɛvɪn/ lay-oh-NEED LEV-in; Russian: Леони́д Анато́льевич Ле́вин; Ukrainian: Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist.
  He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.  He obtained his master's degree at Moscow University in 1970  where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972.
  He and Stephen Cook independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook–Levin theorem, was a basis for one of the seven Millennium Prize Problems declared by the Clay Mathematics Institute with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in computer science and an important step in the development of the theory of computational complexity.
  Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity. His life is described in a chapter of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.
caption: Leonid Levin in 2010
exif: {"Image ImageDescription": "", "Image Make": "Canon", "Image Model": "Canon PowerShot SX120 IS", "Image Orientation": "Horizontal (normal)", "Image XResolution": "180", "Image YResolution": "180", "Image ResolutionUnit": "Pixels/Inch", "Image Software": "Adobe Photoshop CS4 Windows", "Image DateTime": "2010:09:23 03:09:52", "Image YCbCrPositioning": "Co-sited", "Image ExifOffset": "276", "Thumbnail Compression": "JPEG (old-style)", "Thumbnail XResolution": "72", "Thumbnail YResolution": "72", "Thumbnail ResolutionUnit": "Pixels/Inch", "Thumbnail JPEGInterchangeFormat": "1198", "Thumbnail JPEGInterchangeFormatLength": "3777", "EXIF ExposureTime": "1/50", "EXIF FNumber": "14/5", "EXIF ISOSpeedRatings": "400", "EXIF ExifVersion": "0221", "EXIF DateTimeOriginal": "2010:09:22 09:46:44", "EXIF DateTimeDigitized": "2010:09:22 09:46:44", "EXIF ComponentsConfiguration": "YCbCr", "EXIF CompressedBitsPerPixel": "3", "EXIF ShutterSpeedValue": "181/32", "EXIF ApertureValue": "95/32", "EXIF ExposureBiasValue": "0", "EXIF MaxApertureValue": "95/32", "EXIF MeteringMode": "Pattern", "EXIF Flash": "Flash did not fire, auto mode", "EXIF FocalLength": "6", "EXIF FlashPixVersion": "0100", "EXIF ColorSpace": "sRGB", "EXIF ExifImageWidth": "884", "EXIF ExifImageLength": "844", "Interoperability InteroperabilityIndex": "R98", "Interoperability InteroperabilityVersion": "[48, 49, 48, 48]", "Interoperability RelatedImageWidth": "3648", "Interoperability RelatedImageLength": "2736", "EXIF InteroperabilityOffset": "1048", "EXIF FocalPlaneXResolution": "1824000/113", "EXIF FocalPlaneYResolution": "273600/17", "EXIF FocalPlaneResolutionUnit": "2", "EXIF SensingMethod": "One-chip color area", "EXIF FileSource": "Digital Camera", "EXIF CustomRendered": "Normal", "EXIF ExposureMode": "Auto Exposure", "EXIF WhiteBalance": "Auto", "EXIF DigitalZoomRatio": "1", "EXIF SceneCaptureType": "Standard"}