## NP-COMPLETE and NP-HARD

Now we are ready to discuss the class of NP-HARD problems. Let denote that is polynomial time reducible to . Then:

 NP-HARD

Then we can define NP-COMPLETE:

 NP-COMPLETE   NP   NP-HARD

That is, NP-COMPLETE are the set of the hardest of the NP problems, and the easiest of the NP-HARD problems. This is a particularly important class of problems. Typically, we can show that a problem is NP-HARD by showing that for every problem , . Then we can show that . Then it must be in the intersection of the two sets.

Menaka Lashitha Bandara 2005-04-18