2
$\begingroup$

I am currently looking into the $k$-Sum Problem and some of its variants. However i stumbled onto an inconsistency, that i can not seem to fix.

If we begin with $3$-Sum, the 'textbook'-definition goes something along the way of

Let a set $S$ of $n$ integers be given. Are there $a,b,c\in S$ such that $a+b+c=0$.

From this definition however it is not immediatly clear, whether $a,b$ and $c$ have to be distinct. Compare this to this paper. In the Introduction they state

The $k$-SUM problem is the parameterized version of the well known NP-complete problem SUBSET-SUM,and it asks if in a set of $n$ integers, there is a subset of size $k$ whose integers sum to $0$.

This seems to imply, that duplicates are not allowed, as sets usually dont permit duplicates. However in Section 2.2 of the same paper they reduce $k$-SUM to $k$-Table-SUM and link to Section 3.1 of this paper, where the reduction only works in the case, where duplicates are allowed.

Are these two variants equivalent? If so, are there possibly any sources on this? And furthermore, is $k$-Table-SUM NP-hard? Intuition and "closeness" to the $k$-SUM would suggest this, but i haven't found a proof for this apart from the linked sources with the noted inconsistencies.

Thanks!

Edit:

I finally found two sources that can answer this properly. The first contains a reduction from 'Perfect Code' to $k$-SUM without duplicates, however the k-SUM instance is constructed in a way, that allowing duplicates wouldn't find any other solution here (specifically at 22.5.3). In case anyone is not familiar with perfect code, at 22.2.1 the authors reduce Indepenent Set to Perfect Code.

The second source actually links to the first. They reduce $3$-SAT to $k$-SUM in Theorem 5.1. Note that the proof specifically states, that they seperate the instance into d blocks, and then make sure that $k$-SUM only finds one entry per block. This is exactly the same as $k$-Table-SUM and also easily reduced to $k$-SUM with duplicates, similar to the accepted answer.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Yes in case of 3-sum problem they are equivalent. Let $P$ be the version where the three numbers have to be distinct and $P'$ the version where you can use the same number multiple times. The reduction $P'$ to $P$ is by solving the cases with overlapping in preprocessing (since both overlapping cases can be done in almost linear time).

The other direction is a bit more complicated. We will reduce $P$ to another variant $P''$ and from $P''$ to $P$. We start by defining $P''$: given three sets of integers $A,B,C$. Can we pick a number from each to sum to zero.

$P''$ to $P'$ is quite easy. Let $M$ be the largest number in all sets. Let $U := 3M + 1$ build the set $$S := \{a+U:a\in A\} \cup \{b + 2U: b\in B\} \cup \{c-3U:c\in C\}$$ as input to $P''$. Try to prove why the reduction is correct as an exercise.

Now the last reduction from $P$ to $P''$ is a bit more complicated. It is actually randomized. Fix a correct tripple in $S$. A random partition of $S := A\dot\cup B \dot \cup C$, we will have the numbers in the triple assigned to distinct sets with probability at least $2/3 \cdot 1/3 = 2/9$. By repeating a constant factor of $\log n$ you get a running time of $O(n\log n)$ reduction with high probability.

$\endgroup$
3
  • 1
    $\begingroup$ Interesting, thank you for your input! I have actually proven this redcution from $P''$ to $P'$ in the more general case of $k$-sum already. And your randomized reduction in the end should also work for $k$-sum with a probability of $k!/k^k$. Are you aware of a derandomized approach? $\endgroup$ Feb 25, 2020 at 15:10
  • $\begingroup$ No not really. I would find it interesting if you found one. Please post any new resources you find :) $\endgroup$ Feb 25, 2020 at 17:07
  • 1
    $\begingroup$ I've edited the question for two sources that do not necessarily answer the derandomized reduction, but answer the NP-hardness on $k$-SUM with duplicates. $\endgroup$ Feb 26, 2020 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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