This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.
In 1971, in Toronto, Stephen Cook presented a short paper at a computing conference with a plain, unglamorous title: The Complexity of Theorem-Proving Procedures. In it he identified a property that a huge and seemingly unrelated family of hard problems all shared, and showed that one particular problem, Boolean satisfiability, was, in a precise sense, at least as hard as every problem in that entire family put together. Solve it efficiently and you would have solved thousands of other famously stubborn problems for free. This idea, now called NP-completeness, became the organizing concept of an entire branch of computer science, and the still-unresolved question it opens onto, whether such problems can ever actually be solved efficiently or merely checked efficiently once solved, is the P versus NP problem, one of mathematics' seven Millennium Prize Problems. What makes the story more remarkable than the result alone is who else was working on it, and how little either man knew of the other. In 1973, on the other side of the Iron Curtain, in the Soviet Union, a young mathematician named Leonid Levin published a paper called Universal Search Problems, written in Russian, establishing essentially the same idea by a different route, apparently without knowledge of Cook's paper and without any real means of finding out about it quickly if he had wanted to; Cold War science moved between the two blocs slowly, filtered, and late, when it moved at all. Levin was a student of the great Soviet mathematician Andrey Kolmogorov, and his independent arrival at the same foundational insight, in a completely separate scientific culture with its own journals, its own conferences, and its own political pressures on who was allowed to publish what, is not a footnote to Cook's achievement. It is a second, separately confirmed sighting of the same mathematical truth, which is exactly the kind of evidence that convinces mathematicians an idea was really there to be found rather than merely invented by one clever person's particular way of looking at things. The result is now named for both of them, the Cook-Levin theorem, an unusually generous piece of naming in a field not always generous about credit, and one that quietly commemorates something larger than either man's specific proof: two people, unable to read each other's work, arrived at the same door from opposite directions of the twentieth century's deepest political divide, and it is difficult, faced with that, to believe mathematical truth cares very much which side of a wall a mind happens to sit on.