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$
  • 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?)

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

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