0
$\begingroup$

Subset sum is given by this question: "The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?"

My question is: If the numbers in the set are functions of other numbers, is that still subset sum? For example The set {1,2,3} where the first number is X, the second is X+1, third is X+2 and so on. So it is a general set.

Is this allowed?

$\endgroup$

closed as unclear what you're asking by D.W., Yuval Filmus, FrankW, David Richerby, Rick Decker Apr 15 '14 at 23:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ I cannot understand your example: is the set $\{1,2,3\}$ or $\{x+1,x+2,x+3\}$? $\endgroup$ – Yuval Filmus Apr 13 '14 at 23:41
  • 1
    $\begingroup$ Can you clarify what kind of "functions of other numbers" you are interested in? $\endgroup$ – Juho Apr 13 '14 at 23:43
3
$\begingroup$

A set such as $\{1,2,3\}$ is valid input to the problem you defined, so yes, it is "allowed". When setting such constraints, you typically want to know "does the problem still remain NP-complete?". In this sense, notice there is a difference between "can my input take form such as this" and "if my input always takes this form, is the problem still NP-complete?"

I believe you are after the latter; if you impose some constraints on the input, does the problem remain NP-complete? For example, if your input is the set $\{1,\ldots,n\}$ for some positive integer $n$, the answer is no, the problem can easily be decided in polynomial time (can you see why?)

$\endgroup$
  • $\begingroup$ Because all numbers are positive? But the algorithm does not know this. Why is it no? $\endgroup$ – saadtaame Apr 13 '14 at 23:26
  • $\begingroup$ @saadtaame What algorithm are you referring to? I only said there is some algorithm that decides such a variant of subset-sum easily. In other words, in this variant we are given an integer $n$, and have to decide if there is a subset of $[n]$ that sums up to zero. $\endgroup$ – Juho Apr 13 '14 at 23:31
  • $\begingroup$ Any algorithm that solves the general problem. I agree with you but how does this answer the OP's question? I did not get your second paragraph. The OP wants the input to be a variable $x$ and a set $\{x, f_1(x), \dots, f_n(x)\}.$ $\endgroup$ – saadtaame Apr 13 '14 at 23:36
  • $\begingroup$ @saadtaame The second paragraph shows this particular variant is easy. It is unclear to me what the OP really wants ("what functions of other numbers?") $\endgroup$ – Juho Apr 13 '14 at 23:42
  • $\begingroup$ Functions of other numbers in the set. He uses a shift function as an example. He wants to know if these $\{x, x+1, x+2\}$, $\{e^x, sin(x), cos(x), 2, 5\}$ are valid inputs.. $\endgroup$ – saadtaame Apr 13 '14 at 23:51
1
$\begingroup$

The problem SUBSET-SUM is defined usually as follows. An input string belongs to the language SUBSET-SUM if it is a space-separated list of numbers encoded in binary, denoted $x_0,\ldots,x_n$, such that some subset of $\{x_1,\ldots,x_n\}$ sums to $x_0$ (this differs from your account since we don't necessarily have $x_0 = 0$). An instance of SUBSET-SUM is an informal notion meaning a space-separated list of numbers encoded in binary.

Even more informally, the problem SUBSET-SUM is to decide, given a list $x_0,\ldots,x_n$, whether $x_0$ is the sum of some subset of $\{x_1,\ldots,x_n\}$. This notion is used in reductions. Suppose, for example, we want to show that PARTITION is NP-hard. An input string belongs to the language PARTITION if it is a space-separated list of numbers encoded in binary, denoted $x_1,\ldots,x_n$, such that some subset of $\{x_1,\ldots,x_n\}$ sums to $(x_1 + \cdots + x_n)/2$. This reduces to the SUBSET-SUM instance $(x_1+\cdots+x_n)/2,x_1,\ldots,x_n$. What this really means is that there is a polynomial time function $f$, such that $x \in \mathrm{PARTITION}$ iff $f(x) \in \mathrm{SUBSET-SUM}$, which implements the following algorithms:

  1. Attempt to decode the input $x$ to a list of numbers $x_1,\ldots,x_n$. (These are supposed to be encoded as space-separated binary integers.)
  2. If unsuccessful, output 1 (or any other string not in SUBSET-SUM, such as 1 2).
  3. If successful and $x_1+\cdots+x_n$ is odd, output 1.
  4. If successful and $x_1+\cdots+x_n$ is even, output the concatenation of the binary representation of $(x_1+\ldots+x_n)/2$ followed by a space () followed by $x$.

The description of this reduction uses variables, but the output string itself is just a list of numbers encoded in binary as a space-separated string. Any other input format does not constitute a well-formed instance of SUBSET-SUM.

You can define more general versions of SUBSET-SUM, for example allowing variables. These versions will always be NP-hard (since SUBSET-SUM is a special case), and usually also NP-complete.

$\endgroup$
1
$\begingroup$

A set of integers that does not contain functions can be converted into a set of the form your describe by multiplying every element in the set by $x$. Conversely, you can convert a set that contains functions by letting $x=1$ (assuming the functions are defined at 1) and evaluating the functions. So the two problems are equivalent.

$\endgroup$

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