# Multiple subset sum where subsets have complementary cardinality

$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem:

Input: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$.

Output: $k$ $\mbox{ }\underline{not\mbox{ }necessarily\mbox{ }disjoint}$ subsets of $a_i$s of sizes $n_1,\dots,n_k$ satisfying $\sum_{i=1}^kn_i=n$ such that each subset sums to $b$.

(1) Is $\mathsf{EkCSS}$ $NP$-complete?

(2) If we replace requiring $k$ subsets by requiring $\lceil\log^cn\rceil$ subsets for some fixed $c\in\Bbb R^+$ does the problem remain NP complete?

(3) Is $\mathsf{EkCSS-Diff}\mbox{ }$ $NP$-complete where $\mathsf{EkCSS-Diff}$ is same as $\mathsf{EkCSS}$ but with added condition $n_i\neq n_j\forall i\neq j$ (different subset sizes)?

This is a reduction (attempt :-) from this slight variant of SUBSET SUM (which should be NPC) to prove that E2CSS is NP-complete:

Given integers $A = a_1,a_2,...,a_n\;; a_i > 0$ (with the additional constraint that n is even) and a target sum $b$. Does exist $X \subseteq A$ such that $|X|=2m, m \geq 1$ (i.e. $|X|$ is even and greater than or equal to 2) and $sum(X)=b$?

Reduction: suppose that $2^k > b+\sum_{i=1}^n |a_i|$; then we expand $A$ adding a dummy solution

$A' = A \cup \{ -2^k, 2^k + b\}$

If $X$ is a solution for the original problem, then $X, Y= \{ -2^k, 2^k + b\}$ are two distinct solutions for $A'$ and target sum $b$. Now we can further expand $A'$ to $|A''|$ adding padding pairs of integers that do not affect the sums but can be used to "pad" $X$ and $Y$ up to $|X|+|Y|=|A''|$. We have $|A'|=n+2$, so we add $n/2-1$ pairs $\{2^{k+i},-2^{k+i}\}$, $i=1..n/2-1$:

$A'' = \{a_1,...,a_n,-2^k, 2^k + b, 2^{k+1},-2^{k+1},...,2^{k+n/2-1},-2^{k+n/2-1}\}$, $|A''|=2n$

Using all the $n/2-1$ padding pairs we can build a set $Z$ such that $sum(Z)=0$ and $|Z|=2(n/2-1)=n-2$.

We can notice that using the dummy solution and the padding pairs we can build a set $Y'=Y \cup Z$, $sum(Y')=b$, $|Y'|=n$ (which is half the size of $A''$). So in order to get another different solution we must use two or more of the $a_i$ plus some padding pairs.

In the figure a binary expansion of the elements of $A''$:

The above reduction works for any fixed $k$: just start with the (NP-complete) subset sum variant in which $k$ divides $n$ and $|X|\geq k$, then add $k-1$ dummy solutions (each dummy solution made with $k$ elements) and $(n/k-1)$ padding k-tuples.

If $k$ is part of the input (EkCSS), we have a simple generalization of the E2CSS problem and its NP-hardness follows immediately by the NP-completeness of E2CSS; the reduction is trivial: given an instance $A'',b$ of the E2CSS problem, just transform it to $A'',b,k=2$ which is a valid instance of the EkCSS problem. So EkCSS is NP-complete.

(Very informally) The EkCSS-diff should be NP-complete, too and the reduction from EkCSS is: "attach" to every $a_i$ a group of elements $T_i$ of size $m_i=(i+1)*n$:

$T_i= \{ a_i+1*2^u, 2*2^u,3*2^u,....,(m_i-1) 2^u,-2^u*\sum_{j=1}^{m_i-1} \}, |T_i|=(i+1)*n$

The first element of $T_i$ which replaces $a_i$, contains two detached "bit components" the original $a_i$ and $1*2^u$; but the only way to "clear" $1*2^u$ is to include the other elements of $T_i$ and the final one that is the only negative element (it "clears" all the previous $2^u$ components).

Every $T_i$ have distinct values for $u$ (and choosen in such a way that the sums don't interfere with each other and with the sum of the original $a_i$s).

• Thankyou. Does the expansion trick work if we replace $2$ with $3,4,...$ or general $k$ or $\log^cn$?
– Mr.
Nov 30 '13 at 17:46
• I think that the same argument can be applied to any fixed $k\geq 2$ (it is easy to see that the corresponding starting subset sum variants are still NPC ). If you use $k$ as a parameter (or $\log^c n$) then you must "embed" the reduction from SUBSET SUM to the starting SUBSET SUM in which it is required that $n$ is a multiple of $k$ and the size of the solution subset is still a multiple of $k$ (add shifted $a_i$ $k$-times and use as target $b$ the bitwise or of the shifted $b$). If you want I can expand this part and further formalize the proof. P.S. are you using it in another context? Dec 1 '13 at 9:26
• "are you using it in another context?" yes can the n' in your answer be not multiple of base n? I have not fully checked if n'=nk will be fine for me (but something tells it may be better). Could you formalize the proof?
– Mr.
Dec 1 '13 at 9:54
• Yes absolutely. I think the approach simplifies many other related proofs as well(your whole proof could be reduced to a sentence or two if argued precisely), that have been shown to be NPC and another thing that seems interesting is it works if we replace $a_i\in\Bbb Z$ with $a_i\in\Bbb F_p$ and it also seems extendable to counting problems. Give me some time. I am working on some applications and I am writing some other work. I will get back to you with details.
– Mr.
Dec 3 '13 at 15:50
• Perfect, if you want to contact me, my email is marziodebiasi [at] gmail [dot] com . Dec 3 '13 at 16:11