Few technical lerms have gained such rapid notoriety as the appela
tion "NP-complete." In the short lime since its introduction in the early
1970's, this term has come to symbolize the abyss of inherent intractability
that algorithm designers increasingly face as they seek to solve larger and
more complex problems. A wide variety of commonly encountered prob
lems from mathematics, computer science, and operations research are now
known to be NP-compIete, and the collection of such problems continues to
grow almost daily. Indeed, the NP-complete problems are now so pervasive
that it is important for anyone concerned with the computational aspects of
these fields to be familiar with the meaning and implications of this concept
This book is intended as a detailed guide to the theory of NP-
completeness, emphasizing those concepts and techniques that seem to be
most useful for applying the theory to practical problems. It can be viewed
as consisting of three parts.
The first part, Chapters 1 through 5, covers the basic theory of NP-
completeness. Chapter 1 presents a relatively low-level introduction to
some of the central notions of computational complexity and discusses the
significance of NP-compleieness in this context. Chapters 2 through 5 pro
vide the detailed definitions and proof techniques necessary for thoroughly understanding and applying the theory.
The second part. Chapters 6 and 7, provides an overview of two al
ternative directions for further study. Chapter 6 concentrates on the search
for efficient "approximation" algorithms for NP-complete problems, an area
whose development has seen considerable interplay with the theory of NP-
completeness. Chapter 7 surveys a large number of theoretical topics in
computational complexity, many of which have arisen as a consequence of
previous work on NP-completeness. Both of these chapters (especially
Chapter 7) are intended solely as introductions to these areas, with our ex
pectation being that any reader wishing to pursue particular topics in more
detail will do so by consulting the cited references.
The third and final part of the book is the Appendix, which contains
an extensive list (more than 300 main entries, and several times this many
results in total) of NP-complete and NP-hard problems. Annotations to the
main entries discuss what is known about the complexity of subproblems
and variants of the stated problems.
