# Direction of restriction for NP hard proves

I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that problem.

I am wondering shouldn't that be another way around? I mean if you show your problem is a special case of a NP-complete problem, then you showed it is NP complete as well? I know this logic is wrong but why?

Comment: this question actually contents the answer for why we need to reduce a problem to a NP hard problem to prove its NP hardness.

The technique your top paragraph shows NP-hardness. The technique in your next paragraph shows membership in NP.

• ohhhh, so this technique shows certain problem is NP hard? and also the membership in NP means NP complete? Okay I am messing up with NP complete, NP hard, NP hardness and membership in NP. I know the difference between NP complete and NP hard, but i am twisted again. – RandomStudent Jan 12 '15 at 2:11
• Right. $\;\;\;\;\;$ NP-complete $\;\; \iff \;\;$ NP-hard $\:$ and $\:$ in NP $\;\;\;\;\;\;\;\;\;\;$ – user12859 Jan 12 '15 at 2:27
• Wow okay, you made this a lot better! so the first technique shows the problem is NP hard by showing some NP complete problem is a part of it right? then true it is a good way to show it is NP hard. But how can you then show the membership of NP by restriction? the way you do the restriction? further more what if P $\neq$ NP then the restriction i described in the first paragraph might not at all right? sorry I have too many silly questions. – RandomStudent Jan 12 '15 at 2:40

as @Ricky Demer suggested, the restriction only shows you the NP-hardness, you also needs to show the problem belongs to NP in case to you want tho show the NP-completeness.

To show some problem is NP-hard, you need to prove worst case scenario is NP hard.

If you can show a NP hard problem is a special case for the problem you want to prove, then it that problem is also NP-hard. Because this special case showed the worst case is at least NP hard.

Of course there might be other cases in a NP hard problem that can be solved in polynomial time, but those are not the worst cases.

So regardless of the relation between P and NP, restriction is correct.

The technique you showed in your 2nd paragraph is not sufficient, Because as what I wrote in the previous paragraph, the problem you need to prove can be a case solvable in P as well, hence you cannot say it is NP-hard.

In addition, as long as you can find a proven NP hard special case for your problem, and the proof is easier than reduction or any other method, then it is a good idea to use restriction.

From RandomStudent: the reduction actually works in a similar way.

Have fun with cs :)

• forgive my broken English, glad I can help, and you should read the concept more carefully. – HenryHey Jan 16 '15 at 12:58