1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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, 2020 at 15:47
  • $\begingroup$ @VladislavBezhentsev For the knapsack formulation, shouldn't it say "with maximum sum of weights is not greater than $W$"? $\endgroup$
    – Neel Sandell
    Apr 27, 2022 at 20:58

1 Answer 1

Reset to default
1
$\begingroup$

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$?

Improve this answer
$\endgroup$
8
  • $\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, 2020 at 15:53
  • $\begingroup$ That is exactly correct :D! $\endgroup$
    – Jan Chomiak
    Dec 10, 2020 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, 2020 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, 2020 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, 2020 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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