NP-COMPLETE and NP-HARD

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

$$= \left\{\Phi_2 : \forall \Phi_1 \in NP, \exists f \in P, \Phi_1 (i) \leq_P \Phi_2 (f(i)) \right\}$$

Then we can define NP-COMPLETE:

$$= \cap$$

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 $\Phi$ is NP-HARD by showing that for every problem $\Psi \in NP$, $\Psi \leq_P \Phi$. Then we can show that $\Phi \in NP$. Then it must be in the intersection of the two sets.