Levin easily deserves the award alone for his amazing two-page 1971 paper, actually two major research lines
- An independent discovery of NP-completeness and
- Universal search
Levin did so much more, from the "right" definition for average-case hardness to (with Hastad, Impagliazzo and Luby) producing pseudorandom generators from any one-way function.
Congrats to Leonid!