214 NONDETERMINISTIC ALGORITHMS
p to now, all of the algorithms we have considered have solved their
problems in a reasonable amount of time. These problems all have an
order that can be expressed by some polynomial equation. In some
cases, we have seen algorithms that had linear time, like sequential search,
where if the list size doubled, the amount of time the algorithm would take
also doubled. We have seen algorithms that had O(N^2 ) time, like some of the
sort algorithms, where if the list size doubled, the amount of time the algo-
rithm would take would go up by a factor of 4. And we have seen algorithms
that had O(N^3 ) time, like matrix multiplication, where if the size of the matrix
doubled, the amount of time the algorithm would take would go up by a fac-
tor of 8. Even though these increases can be significant, they are still relatively
controlled. The difference this makes can be seen in Figs. 1.1 and 1.2.
In this chapter, we will look at a set of problems that have run times that are
factorial O(N!) and exponential O(xN) (x≥ 2). In other words, these are prob-
lems for which there is no known algorithm to solve the problem in a reason-
able amount of time. We will see that the only way to find a correct or optimal
solution will be to guess at the answer and check to see if it is correct.
Even though these problems take a long time to solve, we can’t just dismiss
them because they have important applications. These problems are needed to
decide on an efficient route for delivery trucks, to develop reasonable exam
schedules, and to schedule tasks so that as many deadlines are met as possible.
Because the problems are important but we don’t have a way to quickly get the
correct answer, we will look at approximations of the correct answer in the
next chapter.
This class of problems is called NP. We begin this chapter with an examina-
tion of the class NP. We then look at a set of classic problems that are in the
class NP. The next section looks at the elements of these problems that put
them into the class NP. We finish with a section that looks at the process of
testing our guess solutions.8.1 What is NP?
The algorithms that we worked with in Chapters 1 through 7 have all had a
complexity that was expressible as a polynomial. In fact, all of the algorithmsU