Few technical terms have gained such rapid notoriety as the appela-
tion HNP-complete." In the short time 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-complete, 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.
1