Throughout this book we have encountered problems, such as the traveling salesman problem, for which we couldn't find any efficient algorithm. By the early 1970s, literally hundreds of problems were stuck in this swamp. The theory of NP-completeness provided the tools needed to show that all of these problems were really the same thing.
The key idea behind demonstrating the hardness of a problem is that of a reduction. Suppose that I gave you the following algorithm to solve the Bandersnatch problem:
Bandersnatch(G)
Translate the input G to an instance of the Bo-billy problem Y.
Call the subroutine Bo-billy on Y to solve this instance.
Return the answer of Bo-billy(Y) as the answer to Bandersnatch(G).
It is important to see that this algorithm correctly solves the Bandersnatch problem provided that the translation to Bo-billy always preserves the correctness of the answer. In other words, the translation has the property that for any instance of G, Bandersnatch(G) = Bo-billy(Y). A translation of instances from one type of problem to instances of another type such that the answers are preserved is called a reduction.
Now suppose this reduction translates G to Y in O(P(n)) time. There are two possible implications:
is a lower bound on computing
Bandersnatch, meaning there definitely exists no faster way to solve it,
then 
must be a lower bound
to compute Bo-billy.
Why?
If I could solve Bo-billy any faster,
then I could solve Bandersnatch
in faster time by using the above simulation, thus violating my lower bound.
This implies that there can be
no way to solve Bo-billy any faster than claimed.
This second argument is the approach that we will use to prove problems hard. Essentially, this reduction shows that Bo-billy is at least as hard as Bandersnatch, and therefore once we believe that Bandersnatch is hard, we have a tool for proving other problems hard.
Reductions, then, are operations that convert one problem into another. To describe them, we must be somewhat rigorous in our definition of a problem. A problem is a general question, with parameters for the input and conditions on what constitutes a satisfactory answer or solution. An instance is a problem with the input parameters specified. The difference can be made clear by an example. The traveling salesman problem is defined thus:
Input: A weighted graph G.
Output:
Which tour 
minimizes 
?
Thus any weighted graph defines an instance of TSP. Each particular instance has at least one minimum cost tour. The general traveling salesman problem asks for an algorithm to find the optimal tour for all possible instances.
Any problem with answers restricted to yes and no is called a decision problem. Most interesting optimization problems can be phrased as decision problems that capture the essence of the computation. For example, the traveling salesman decision problem can be defined thus:
Input: A weighted graph G and integer k.
Output: Does there exist a TSP tour with cost 
?
It should be clear that the decision version captures the heart
of the traveling
salesman problem, for if you had a program that gave fast solutions to
the decision problem, you could do a binary search with different values
of k to quickly hone in on the correct solution.
Therefore, from now on we will talk only about decision problems, because it is easier to reduce one problem to another when the only possible answers to both are true or false.