I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-Knapsack with the value of every item being equal to its weight.
Is this still NP-complete? Or am I missing something?
Asked By : Zeta Two
Answered By : Aryabhata
Yes, this is called the subset-sum problem and is NP-Hard.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11243
0 comments:
Post a Comment
Let us know your responses and feedback