Subset Sum Requirements

Consider the following problem.


Given a set $S$ of integers, a function $f : \mathbb{Z} \to \mathbb{Z}$ and $k \in \mathbb{Z}$, decide wether there is $X \subseteq S$ such that $f\left(\sum_{x\in X}x\right)=k$.

Is this still considered a subset-sum problem?

For instance, given

$\qquad \displaystyle S=\{ −7, −3, −2, 5, 8\}$

and $k=0$, find a subset $X$ such that $f\left(\sum_{x\in X}x\right)=0$ for $f(y)=-3+y$. In this case, a solution is $X=\{ -3,-2,8 \}$.

It depends on the form of $f$. If $f(x) = x$, then it is identical to subset-sum. If $f(x) = 0$, then it is a trivial problem with an $O(1)$ solution: return $true$. You can possibly define $f$ in other ways to make the question more or less difficult, as well.

See below a mini-complexity zoo corresponding to different choices of $f$:

• for $f(x) = c$, the problem is $O(1)$ (return true iff $c = 0$).

• for $f(x) = 0$ for $x \geq 0$ and $f(x) = 1$ otherwise, the problem is $O(n)$ (linear search for any number greater than 0)

• for $f(x) = 0$ for $x \geq c$, $c > 0$, $f(x) = 1$ otherwise, the problem is no more than $O(n \log n$) (sort the items in the set in descending order, and see if any prefix sums to a working solution)

• for $f(x) = ax + b$, the problem is as hard as subset-sum (in an informal sense, and I don't provide a construction to demonstrate the reduction from subset-sum to this... if I'm wrong about this one, please let me know!)

• for $f(x) = 0$ if the Turing machine encoded by $x$'s binary representation halts when given the binary representation of $x$ as input (alternatively, when given the empty tape as input, and similar kinds of halting problems), and $f(x) = 1$ otherwise, the problem is undecidable (a solution to the problem for this $f$ could solve the halting problem)

Anybody see anything else fun?

StackExchange Computer Science Q#1053, answer score: 7