I am working on a problem defined as the following

Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our resources and $G$ is our necessary minimal reward, is there a set $R' \subseteq R$, so that $\sum_{(z,g)\in R'}z \leq Z$ and $\sum_{(z,g)\in R'}g \geq G$?

I want to show its NP-completeness and have shown that it is in NP already. I am struggling with the NP-hardness. My known NP-hard problems are the SAT, 3SAT, partition, subset sum and bin packing.

My struggle seems to be mostly with the fact that we have to balance two different values now, the cost and the reward. This is not the case in any of the set related problems I mentioned and I am unable to think of how to model this in SAT or 3SAT. What am I missing here? How can I show the NP-hardness and as such the NP-completeness of this problem using only these given problems?

  • $\begingroup$ Try to see if there's a special case that's already hard. For instance, could you set $G = $ (or something similar) so that the problem becomes equivalent to a well-known hard problem such as subset sum? $\endgroup$
    – Juho
    Jun 29 '20 at 9:34

This sounds to me like the Knapsack problem where

  • $z$ is the weight of each item,
  • $Z$ is the capacity of the knapsack,
  • $g$ the value of the item, and
  • $G$ the value to be achieved.

The problem is NP-complete but solvable, using dynamic programming, in pseudo-polynomial time $O(n \cdot W)$ where $W = \max_{(z,g) \in R}(g)$.

You can prove that the Knapsack Problem is NP-complete by reducing from the Subset sum problem. Indeed, Subset Sum is a special case of Knapsack where $z = g$; The "weight" of each problem is the same as its "value".

  • $\begingroup$ Indeed, I am surprised that I did not draw this connection. Still, I sadly do not have the Knapsack problem as a basis for my argumentation. I may only use the NP-complete problems given in the question to argument the NP-completeness/hardness of the problem. Do you maybe have an idea for a possible aproach to this? I am still struggling with understanding how I can reduce a problem with only one value to be managed into one that has two such values. I imagine this is not a problem with SAT; but in that case I can't think of a good abstraction to make sense of it. $\endgroup$ Jun 29 '20 at 10:14
  • $\begingroup$ Yes, I have just found this explanation myself after researching the knapsack problem. It definitely showed me how I still have to work on my understanding of the process of reduction, as I did not consider this to be functional before. Thank you very much for leading me on the right path! Very helpful! I would propose adding the explanation of how subset sum is a special case to the answer in order to directly answer my question. Otherwise, perfect! Thank you. $\endgroup$ Jun 29 '20 at 10:49
  • $\begingroup$ Added hint of subset sum being a special case of knapsack. $\endgroup$
    – Pål GD
    Jun 29 '20 at 12:46

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.