7
$\begingroup$

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 \}$.

$\endgroup$
  • $\begingroup$ Isn't $k=0$ without loss of generality? $\endgroup$ – JeffE Apr 5 '12 at 20:20
  • $\begingroup$ @Jeff Seems so. For $f$ and $k \neq 0$, there is an equivalent $f'$ with $k' = 0$. $\endgroup$ – Patrick87 Apr 6 '12 at 2:21
  • $\begingroup$ When exactly do you mean by "Is this still considered a subset-sum problem"? Are you asking whether you can call an instance of such a problem (i.e. given an $f$) as 'a variant of subset sum'? $\endgroup$ – Aryabhata Apr 6 '12 at 8:15
7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 1) "the problem is equivalent to subset-sum" -- do you mean this literally or "as hard as"? 2) In the last bullet you should give $x$ as input to the TM; as it is, you solve some halting problem but not the canonical one. $\endgroup$ – Raphael Apr 5 '12 at 16:57
  • $\begingroup$ 1) Yes, I mean "as hard as", in a sort of informal sense. Of course I don't provide a construction for that, but it seems to be right... of course, I have been surprised before, and this could be wrong. Editing to make this clear. 2) Right, I debated at first whether I should do that or not, but hearing you suggest that it's better that way is enough for me. $\endgroup$ – Patrick87 Apr 5 '12 at 17:11
  • $\begingroup$ Does `as hard as' mean the problem is NP-Complete. Would that make it a reduction of Subset Sum or 3-CNF SAT? Is there a proof laying bare the reducibility of a subset with this special case of having an equation whose values are integers and whose solution is 0? $\endgroup$ – Char Apr 6 '12 at 1:59
  • $\begingroup$ @Patrick87 your second bullet is on par with where my inquiry is leading me. Can you expand on this portion to discuss its NP-Completeness in detail? $\endgroup$ – Char Apr 6 '12 at 2:01
  • $\begingroup$ @Char Subset-sum is a special case of $f(x) = ax + b$ (let a = 1, b = 0). To see the other reduction, solve for $f(x) = x + b/a$ after dividing all set elements by a (problem is scale invariant). As others have pointed out, it's already well-known that the problem with $f(x) = x + c$ is "as hard as" the canonical subset-sum (that is, where $f(x) = x$). $\endgroup$ – Patrick87 Apr 6 '12 at 2:28
6
$\begingroup$

You can get arbitrary difficult problems depending on your $f$.

Let $A$ be a language. Define $f$ as follows: $$f(x)= \begin{cases} 0 & x\in A \\ 1 & o.w. \\\end{cases}$$

Consider set $S=\{x\}$. There is a non-empty subset $X\subseteq S$ s.t. $f(\Sigma_{x\in X} x) = 0$ iff $x \in A$.

Without putting a complexity requirement on $f$ you can get problems of arbitrary difficulty.

An interesting case is when $f$ is of restricted complexity, e.g. polynomial time computable. In that case we can use it to invert $f$, so the problems can be as difficult as inverting an arbitrary polynomial time function (and assuming that there are polynomial time computable psuedo-random number generators which are hard to invert in subexponential time, it means you cannot solve the problem): let $g$ be an arbitrary polynomial time computable function. Assume that we are given $y\in Range(g)$ and we want to find an $x$ s.t. $g(x)=y$. Define $f(x)=g(x)$. Let $S= \{0,1,2,4,8,\ldots, 2^m\}$ for suitable large $m$ (to make sure that a preimage of $y$ can be represented as sum of the numbers in the set). At each set we will remove a number $2^i$ from the set and check if there is still a subset $X$ s.t. $f(\Sigma_{x\in X} x)=y$. If the answer is yes, we know there is a solution that doesn't need that number, so we remove it from $S$ permanently. If the answer is no, we know that we need that number for all solutions. After $m$ steps we will have a set $S$ which is a solution and no subset of it is a solution, so we can return $x=\Sigma_{x \in S} x$ as our answer.

On the other hand, if $f$ is polynomial time computable, the problem will be in $\mathsf{NP}$.

In the special case that the function $f$ is linear, since $\Sigma$ commutes with linear functions, the problem is the same as solving the subset-sum over $f(S) = \{ f(x) \mid x \in S\}$. As long as the linear function is not constant the problem will be as hard as subset-sum, i.e. $\mathsf{NP\text{-}hard}$ (if you want to solve the subset-sum instance $(S,k)$, apply $f^{-1}$ to members of $S$ to obtain $S'$ and then use the modified version on $(S',k)$ to solve it).

(This trick will also work for more general case where the function $f$ is polynomial time computable and has an inverse that is also polynomial-time computable.)

$\endgroup$
  • $\begingroup$ if arbitrary, how do I determine if my function will produce an NP-hard complexity? The linearity? Can you source a proof of this? Also, what do you mean on the other hand'? Your restricted complexity example uses polynomial time computability as your restriction, and then you suggest on the other hand' but continue talking about polynomial time computability? Also, in your last paragraph I was confused by the comment `as long as the linear function is not constant', but isn't the subset sum problem constant in nature? 0, or 1? Thanks for the thorough reply. $\endgroup$ – Char Apr 7 '12 at 9:11
  • $\begingroup$ I have assumed in my answer that $f$ is a priory fixed function. If you want it to be part of the input, then you have to define how $f$ is given first. Let's say it is given as a finite string which is the code of a Turing machine computing it, then you cannot. You should ask a separate question if you want to know why complexity of a given Turing machine is not a decidable problem. $\endgroup$ – Kaveh Apr 7 '12 at 17:11
  • $\begingroup$ "Can you source a proof of this?" I don't understand what you mean. $\endgroup$ – Kaveh Apr 7 '12 at 17:12
  • $\begingroup$ "On the other hand" is still about polynomial time $f$, the difference is that it is giving an upper bound on the complexity of the problem. $\endgroup$ – Kaveh Apr 7 '12 at 17:13
  • $\begingroup$ If $f$ is a constant function, then the problem is trivial since independent of what $X$ you select, $f(\Sigma_{x \in X}x)$ will be the same. "isn't the subset sum problem constant in nature? 0, or 1?" again, I don't understand what you mean. $\endgroup$ – Kaveh Apr 7 '12 at 17:14
0
$\begingroup$

Yes, this is still subset sum problem, but instead of finding a subset whose sum is $0$, you are required to have a sum that equals something else (in your example it 3, in general it is $f^{-1}(0)$, which might be a set of numbers if $f$ is many to one).

This doesn't change much the difficulty of the problem for bijective $f$, but otherwise depends on the number of preimages $f^{-1}(0)$ has. As stated already, if $f(y)=0$, the problem becomes trivial.

$\endgroup$
  • $\begingroup$ The issue here is you are looking for a number x=3 for f(x) to equal 0, but you do not know that is the value you require, and instead of solving the equation you use a subset sum to find the value by testing to see if the function returns 0. $\endgroup$ – Char Apr 6 '12 at 1:09
  • 2
    $\begingroup$ You should edit the question to clarify this point. As said, everything depends on $f$. If you don't "know" it (but only has an black-box access to it, the answer is different (as demonstrated by @patrick87) $\endgroup$ – Ran G. Apr 6 '12 at 1:43
  • $\begingroup$ You know $f$, you do not know $x$. Can you suggest a rewrite to the question. I have the handicap of knowing what I meant and am finding it difficult to reword the question to clarify any further. What is still unclear to those reading it? $\endgroup$ – Char Apr 6 '12 at 1:49
  • $\begingroup$ I'm not sure I fully understand what you're looking for. If you know $f$, (assuming it is simple), why can't you invert it to find its root (the value x that makes $f(x)=0$, and then solve the subset-sum with this value as target? $\endgroup$ – Ran G. Apr 6 '12 at 1:52
  • 1
    $\begingroup$ @RanG. Simple functions are not necessarily simple to invert. See all of public-key cryptography! $\endgroup$ – JeffE Apr 6 '12 at 7:12

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.