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:

    NP-HARD$\displaystyle = \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:

    NP-COMPLETE$\displaystyle =$   NP$\displaystyle \cap$   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 $ \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.



Menaka Lashitha Bandara 2005-04-18