218 NONDETERMINISTIC ALGORITHMS
in polynomial time and the second problem can be solved in polynomial
time, we know that our new problem also has a polynomial time solution.
Let’s look at an example of this that will make the process clearer. Our first
problem will be to return “yes” if any of a group of Boolean variables has a
value of true and return “no” if all are false. The second problem is to find the
largest value in a list of integers. You should be able to see a very clear and easy
solution for each of these problems, but for the sake of this example, let’s say
that we have a solution to the largest integer problem but not for the Boolean
variable problem. We can solve the Boolean variable problem by reducing it to
the largest-integer problem. We begin by taking an instance of the Boolean
variable problem and writing a conversion algorithm that will, for each Bool-
ean variable, assign the next list entry the value of 0 if the Boolean variable is
false, and a value of 1 if the Boolean variable is true. We now use our algorithm
to find the largest value in the list. You should see that the answer will be either
0 or 1 because of how we set up the list. We now convert this answer back into
a solution to the Boolean variable problem by returning yes if the largest value
is 1 and returning no if the largest value is 0.
In Chapter 1, we saw that finding the largest value in a list can be done in
linear time, and we see that our reduction can also be done in linear time;
therefore, the Boolean variable problem must also be solvable in linear time.
In the next section, we will use this technique to learn some thing about
NP problems. We will see, however, that the reductions of NP problems can be
much more involved that this.■ 8.1.2 NP-Complete Problems
When discussing the class NP, we must remember that we might think these
problems take a long time to solve because we just haven’t found a faster algo-
rithm to solve them. If we thought about the traveling salesperson problem dif-
ferently, perhaps we could develop a deterministic algorithm that could solve it
in polynomial time. The same could be said about any of the problems that we
will consider in the next section.
The term NP-complete is used to describe the hardest of the problems in the
class NP. These problems are singled out because if at any point we find a
deterministic polynomial time algorithm for one of them, all of the problems
in NP must have deterministic polynomial time algorithms.