reductionnpnp-completenp-hard

When L2 is NP complete, and L1 can be reduced to L2


If L2 is NP complete and L1 ≤p L2, I can see that L1 is NP at any time. And I believe L1 could possibly be NP hard (though not all the time). Now my question is, it seems like at some cases NP hard are reducible to NP. I'm just not sure if my assumption is right and might need a clarification.


Solution

  • Problem is in NP means: there is an algorithm that runs in NP to solve the problem. Problem is NP-hard means: this problem is "at least as hard as the hardest problems in NP" Problem is NP-complete means: this problem is in NP and is NP-hard.

    So with polynomial-time reduction of an NP-hard problem L1 to another problem L2, you prove that L2 is NP-hard as well. But in this case L2 is not necessary in NP.