The following problems live in integer domain.

I want to find a subset of $\{x_0, x_1, \ldots, x_{n-1}\}$ such that the subset's elements sum to any number in a prescribed interval $[X,X+k]$, $k\geq 1$.

We call the above problem A.

An obvious approach is to solve $k+1$ standard subset sum problems with targets $X, X+1,\ldots,X+k$ . I would be satisfied once my algorithm finds a solution to any of these problems.

Now I am wondering, does there exist a single standard subset problem B: $\{y_0,y_1,\ldots,y_{m-1};Y\}$ where $Y$ is the target, such that if I solved B, I equivalently solved A, additionally, the conversion from B's solution to A's solution is fast, preferably in linear time.

To make it simpler, I am only considering $k=1$.

Thank you!

  • 1
    $\begingroup$ What do you think? Have you tried constructing such a reduction? $\endgroup$ – Yuval Filmus Jun 3 '18 at 20:37
  • $\begingroup$ Given that your problem is in NP and that subset sum is NP-hard, there does exist a polytime reduction. $\endgroup$ – Yuval Filmus Jun 3 '18 at 20:37

This answer assumes that a Yes instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$ is one in which there is a subset summing to either $X$ or $X+1$.

Given an instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$, construct an instance of subset sum with elements $x_0,\ldots,x_{n-1},1$ and target $X+1$. You take it from here.


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.