0
$\begingroup$

I've been given a set $S$ of natural numbers (non-negative integers) $s_1$, $s_2$,...,$s_n$ where $|S|=n$. My problem is to figure out if there is way to get a total sum of 0 when using all the numbers of $S$ but we get to "choose the sign" for each number: that is, for $s_i$ we get to choose if we're going to add or subtract $s_i$ from the total sum.

I've tried visualizing it using a directed cyclic graph with $n$ vertices where the only edges from $v_1$ to $v_2$ are $+/- s_1$ and the task is to traverse the whole graph, ultimately getting back to our starting node $v_1$ using a path with total weight 0.

What would be a suitable NP-complete problem to reduce into this one?

$\endgroup$
  • 1
    $\begingroup$ Hint: PARTITION $\endgroup$ – Pontus Apr 20 '17 at 10:19
  • $\begingroup$ Yes of course, that actually makes perfect sense.. I suppose you mean we can find a partitioning into two subsets with equal sum, and then for my application just negate one of them and the total result is zero? $\endgroup$ – Nyfiken Gul Apr 20 '17 at 10:27
  • 1
    $\begingroup$ Exactly. As the differences between your problem and PARTITION are so superficial, one could even reasonably claim that they are the same problem. $\endgroup$ – Pontus Apr 20 '17 at 10:34
  • $\begingroup$ You're absolutely right, it'll be a piece of cake from now on :) Thanks for your help Pontus! If you want to post it as an answer I'd gladly accept it. $\endgroup$ – Nyfiken Gul Apr 20 '17 at 10:46
2
$\begingroup$

This problem is essentially just a rephrasing of the classic NP-complete problem PARTITION. If you can partition a set $S$ of natural numbers into two partitions $S_1$ and $S_2$ with equal sum, then $\sum_{s \in S_1} s + \sum_{s \in S_2} -s = 0$ and vice versa.

$\endgroup$

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.