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.
Asked By : RandomStudent
Answered By : Ricky Demer
The technique your top paragraph shows NP-hardness. The technique in your next paragraph shows membership in NP.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37149
0 comments:
Post a Comment
Let us know your responses and feedback