Leonid Levin

Leonid Levin is a mathematician and computer scientist who independently developed foundational results on NP-completeness and helped establish the theory of average-case complexity.

NP-completeness: A property of problems that are in NP and at least as hard as every problem in NP under polynomial-time reductions. Levin independently established foundational completeness results, alongside Stephen Cook.
Polynomial-time reduction: A transformation between problems computable in polynomial time that preserves their yes-or-no answers. Reductions transfer hardness from known difficult problems to new ones.
Stephen Cook: A computer scientist whose 1971 theorem established Boolean satisfiability as NP-complete. Cook reached the central completeness result independently of Levin.
NP-complete problems: Decision problems in NP to which every problem in NP can be reduced in polynomial time. Levin’s early completeness work belongs to the theory’s initial formation.
Average-case hardness: The property of requiring substantial computational resources on typical inputs under a specified distribution. Levin’s framework raises the challenge of proving robust hardness for natural distributions.
Cook–Levin theorem: The theorem that Boolean satisfiability is NP-complete. Levin proved an independent version establishing the same landmark result.
Nondeterministic Turing machine: A computational model that can branch into multiple possible transitions at each step. NP-completeness is defined using efficient verification or nondeterministic computation.
Andrey Kolmogorov: A Soviet mathematician whose work founded modern probability theory and influenced algorithmic information theory. Levin worked in the research tradition surrounding Kolmogorov’s theory of information.
Soviet mathematics: Mathematical research conducted in the Soviet Union and its institutions during the Soviet period. Levin’s early career developed within Soviet mathematical and computing communities.
One-way function: A function easy to compute but computationally difficult to invert on typical outputs. Average-case hardness is closely tied to the existence of one-way functions.

Linked from 7 pages