2
$\begingroup$

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?

What is the advantage and disadvantage of this technique.

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – RandomStudent Jan 12 '15 at 2:11
  • 1
    $\begingroup$ Right. $\;\;\;\;\;$ NP-complete $\;\; \iff \;\;$ NP-hard $\:$ and $\:$ in NP $\;\;\;\;\;\;\;\;\;\;$ $\endgroup$ – user12859 Jan 12 '15 at 2:27
  • $\begingroup$ 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. $\endgroup$ – RandomStudent Jan 12 '15 at 2:40
2
$\begingroup$

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.

This answer is dedicated to answer your questions in your comment to Mr. Ricky's answer.

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 :)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.