I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem.
Overall I want to show that Knapsack is NP-complete.
There are two parts to showing knapsack is NP-complete

  1. knapsack is in NP
  2. If I show that the subset sum problem is polynomially reducible to the knapsack.
    Then since subset sum problem is known to be NP-hard. Knapsack is NP-Hard

Both 1) and 2) imply that Knapsack is NP-Complete

  1. Is trivial as given any sequence of items we can verify the sum of their value
    and weights in linear time. So the knapsack is in NP. Correct me If I am wrong here.

How do I approach 2)? I am not sure how to phrase the polynomial conversion
from the subset sum problem to the knapsack.

  • $\begingroup$ Both of these problems have a lot of different formulations. For example, for subset sum problem: "Given a multiset $S$ of positive integers and an integer $x$, find whether there is a sub(multi)set of $S$ with sum $x$". And for knapsack: "Given a multiset $S$ of positive integers and integer $W$, find a sub(multi)set of $S$ with maximum sum which is not greater than $W$". Can you see a reduction for such formulations? $\endgroup$ – Vladislav Bezhentsev Dec 10 '20 at 15:47

The subset-sum problem is a pair $(S,k)$ and a question whether there exists $S' \subset S$ such that $\sum_{s \in S'} s = k$.

The knapsack problem is a tuple $(w,v,W, V)$ that is weights, values, the knapsack capacity and the target value, and a question can you pick such a set of items $\mathcal{I}$ such that:

  1. $\sum_{i \in \mathcal{I}} w_i \leq W$
  2. $\sum_{i \in \mathcal{I}} v_i \geq V$

Hint: Given an instance $(S,k)$ of subset-sum, is there a way to set the weights and values of our items in the knapsack, so that these inequalities turn into a single equality related somehow to $k$?

  • $\begingroup$ So if I take all w = v =S and W,V=k then this is an instance of knapsack problem. And a solution to it would give a solution to the subset problem. Is that correct? $\endgroup$ – Ronit sharma Dec 10 '20 at 15:53
  • $\begingroup$ That is exactly correct :D! $\endgroup$ – Jan Chomiak Dec 10 '20 at 16:07
  • $\begingroup$ Is that all ? I mean than the proof is done right? Because knapsack is in NP and I have reduced subset to knapsack and so knapsack is NP Hard. Hence knapsack is NP Complete.. I thought it will be way more tougher than that. Thanks your way of putting the definition helped $\endgroup$ – Ronit sharma Dec 10 '20 at 16:10
  • $\begingroup$ Formally, to prove that a reduction is complete you have to show that every "yes-instance" of language $A$ gets transformed into a "yes-instance" of language $B$, and every "no-instance" into a "no-instance". This reduction is very simple, so the proof is just two lines of reasoning, but there are many reductions which are way more complicated than that $\endgroup$ – Jan Chomiak Dec 10 '20 at 16:12
  • $\begingroup$ I have one more doubt. When a problem is NP complete does that mean that there cannot be any polynomial algorithm for it or no known polynomial time solution is known? $\endgroup$ – Ronit sharma Dec 10 '20 at 16:37

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.