COMBINATORICS, COMPLEXITY, AND RANDOMNESS
Upon reading Cook’s paper, I realized at once that his
concept of an archetypal combinatorial problem was a
formalization of an idea that had long been part of the
folklore of combinatorial optimization. Workers in that
field knew that the integer programming problem,
which is essentially the problem of deciding whether a
system of linear inequalities has a solution in integers,
was general enough to express the constraints of any of
the commonly encountered combinatorial optimization
problems. Dantzig had published a paper on that theme
in 1960. Because Cook was interested in theorem proving
rather than combinatorial optimization, he had chosen
a different archetypal problem, but the basic idea
was the same. However,......
