ABSTRACT
This chapter deals with a large family of integer-factoring problems. This family is not just a list of seemingly difficult computational problems. It is, in fact, bound together by strong structural ties. The collection of problems, called the NP-complete problems, includes many well known and important questions in discrete mathematics, The chapter shows how to develop the formal machinery that will permit us to give precise definitions of all of the concepts that are needed. It discusses the additional ideas informally and precisely. Many of the problems that we are studying can be phrased as decision problems or as optimization problems. Since every decision problem can have only the two answers ‘Y/N,’ we can think of a decision problem as asking if a given word (the input string) does or does not belong to a certain language.
