• restriction,
• local replacement, and
• component design

In this section we shall indicate what we mean by each of these proof types, primarily by giving examples. It would be sheer folly to attempt to define them explicitly...

...

Proof by restriction is the simplest, and perhaps most frequently applicable, of our three proof types. An NP-completeness proof by restriction for a given problem L NP consists simply of showing that L contains a known NP-complete problem L' as a special case. The heart of such a proof lies in the specification of the additional restrictions to be placed on the instances of L so that the resulting restricted problem will be identical to L'. We do not require that the restricted problem and the known NP-complete problem be exact duplicates of one another, but rather that there be an "obvious" one-to-one correspondence between their instances that preserves "yes" and "no" answers."