Now we are ready to discuss the class of NP-HARD problems. Let denote that is polynomial time reducible to . Then:
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.