Leonid Levin is a mathematician and computer scientist whose work helped found the theory of NP-completeness. Working in the Soviet Union in the early 1970s, independently of and at roughly the same time as Stephen Cook in North America, he arrived at the central insight that certain problems in NP are universal: a fast algorithm for one of them would yield a fast algorithm for all of them. This shared discovery is why the foundational result of the field is called the Cook-Levin theorem.
Levin’s path differed sharply from that of his Western counterparts. His results circulated first in the Soviet literature before becoming widely known in the West, and he later emigrated to the United States. His own home page, hosted at Boston University, lists his research interests across the theory of computation, including randomness and nondeterminism, holographic proofs, and average-case complexity, and it links his work to the P versus NP problem, which it notes is one of the seven Millennium Prize Problems.
Beyond the Cook-Levin theorem, Levin is known for early work on universal search and on the foundations of randomness and average-case hardness, themes that run through his Boston University materials. His career is a standard example cited when historians of computing discuss how the same deep idea can emerge independently on opposite sides of a scientific divide.