Rama · CC BY-SA 2.0 fr

A computer scientist whose 1972 paper on NP-completeness gave the field its working vocabulary for what makes a problem hard, identifying 21 problems — from the traveling salesman to graph coloring — that were all, in a precise sense, equally intractable. The work won him the 1985 ACM Turing Award, computing's highest honor, along with the Benjamin Franklin Medal and the Kyoto Prize.