## Chapter 18

## Some NP and NP-Complete Problems

#### Objectives

*After reading this chapter, you should understand:*

*A few important Real Life NP-Hard and NP-Complete Problems in detail*
*An Informal definition of NP-Hardness and NP-Completeness*
*P and NP classes in terms of the Turing Machine*
*Reducibility of problems so that NP Completeness can be proven*
*How to use the notion of reducibility to prove NP-Completeness for several Classical Problems*

#### Chapter Outline

*18.1 Introduction*

*18.1.1 NP-Hardness*

*18.1.2 NP-Completeness*

*18.1.3 Consequences of being in P*

*18.1.4 Reduction Source Problems*

*18.2 Turing Machine (TM)*

*18.2.1 Relation between Problems and Languages*

*18.2.2 Decision Problems and Languages*

*18.3 Reductions*

*18.3.1 Definition of Reductions*

*18.3.2 Reduction ...*