  In 1971, Cook proved SAT is NP complete [Cook, 1971].  Shortly later,  Karp showed that many important combinatorial problems were also NP complete, thus establishing the importance of the class NP [Karp, 1972]. 