1
$\begingroup$

My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is NP-hard ?

For example let say I have the knapsack problem (the weighted version):

$$\max \sum_{i}^n w_i x_i$$ $$\text{s.t.} \sum_{i=1}^n p_i x_i\leqslant W,\quad(WP)$$ $$x_i\in\{0,1\}.$$

This problem is know to be NP-hard problem. However, the unweighted version of this problem is given by: $$\max \sum_{i}^nx_i$$ $$\text{s.t.} \sum_{i=1}^n p_i x_i\leqslant W,\quad(P)$$ $$x_i\in\{0,1\}.$$ is not NP-hard since the optimal solution is to sort the items in the ascending order with respect to $p_i$ and start filling the bag until the capacity $W$ is reached.

The problem is the following: I used the unweighted version of this problem as a special case of the weighted version and I showed that unweighted is an NP-hard problem. What is my mistake? Here is my steps: I will reduce $(WP)$ to $(P)$ in polynomial time. So, an instance of $(P)$ is constructed easily by taking $w_i=1$. And I am done and hence $(P)$ is NP-hard which is obviously wrong.

Thank you to correct me and give me if possible some good references that deal with such weighted and unweighted problems?

$\endgroup$
3
$\begingroup$

No, you cannot prove that the unweighted problem is NP-hard in this way. The error is that you cannot reduce WP to P in polynomial time (without proving P=NP).

Remember what the input to each problem is. For WP, you are given a list of $w_i$ and $p_i$ and must choose a setting of the $x_i$. So once I am given a fixed list of $w_i$ and $p_i$, I would need to come up with an instance of P (which is just a list of $p'_i$) so that the solution tells me the solution to WP.

The key point is that you seem to say that we can just take all $w_i = 1$ to reduce WP to P, but we can't change the $w_i$: They are given as part of the input. It is true that P is the special case of WP where all $w_i = 1$, but the issue is, when we are given an instance with $w_i \neq 1$, we have to solve this instance and we can't change the $w_i$ we are given.

$\endgroup$

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.