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?
NP-hardness proof, what is wrong with it?
complexity theory;optimization;np hard
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.