how were the first NP-complete problems shown to be NP-complete?

Question

From the wikipedia entry on NP-Complete:

"The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it"

I'm pretty sure that I understand this: If I have a problem, I can show that it is NP-Complete if I:

1. show that it is in NP (a solution to the problem can be verified in polynomial time on a non-deterministic Turing machine)

2. Show that a problem already known to be NP-Complete can be 'reduced' to the new problem

So, my question is, how were the first NP-complete problems 'proven' to be NP-complete? At one time, the set of known NP-complete problems must have been zero, and this would have made it impossible to resort to step 2 in the above process.

This makes me think that there is a different method for proof which I'm not aware of. Either that, or maybe the whole NP-complete property is 'assumed' for certain problems due to lack of a known polynomial time solution. (actually, having written this, I wouldn't be surprised if this is the case, but I'd like some guru-feedback either way).

Answer 1

Cook's Theorem

The class NP can be defined as the class of problems decidable by a nondeterministic Turing machine in polynomial time. This theorem shows that SAT is NP-complete by encoding the operation of any nondeterministic Turing machine by a boolean formula, in such a way that the machine accepts if and only if that formula is SATisfiable.

Historically speaking, the notion of NP-completeness was introduced in Richard Karp's seminal paper (Reducibility Among Combinatorial Problems), where he defined NP-completeness, used Cook's theorem, and in one big shot, proved 21 problems NP-complete.