2
$\begingroup$

Given a multiset of integers $S$, in the Equ-Sum problem we want to check whether or not $S$ can be divided into two disjoint subsets, say $X_1$, $X_2$ such that $\sum_{x_i \in X_1}x_i = \sum_{x_j \in X_2}x_j $. In the 3-Equ-Sum problem for given multiset $S$ we want to check whether $S$ can be divided into three disjoint subset say $Y_1$ , $Y_2$ , $Y_3$ such that $\sum_{x_i \in Y_1}x_i = \sum_{x_j \in Y_2}x_j = \sum_{x_k \in Y_3}x_k$ .

as we know both of these problems are NP-complete so both of them can be reduced to each other, a reduction from EQU-SUM to 3-EQU-SUM is obvious as we can add $x = \frac{\sum_{x_i \in S}x_i}{2}$ to $S$ but I'm working on a direct reduction from 3-EQU-SUM to EQU-SUM. can anybody help me?

$\endgroup$
1
  • 2
    $\begingroup$ I can give you a hint. It is easiest to split up the reduction in two steps. First reduce to SUBSET SUM and then to EQU-SUM (aka PARTITION). As a first step think about the following. Let M be a large number, and consider for every x from S the 3 numbers $xM^2$, $xM$, and $x$. Let $N$ be such that $3N$ is the sum of the integers of $S$. A partition in 3 sets gives in a natural way a subset of sum $N(M^2+M+1)$. Now this does not quite work yet, but you should now try to modify the constructed numbers in such a way that you must select exactly one of the 3 generated numbers for every $x$ of $S$. $\endgroup$ May 29, 2020 at 7:58

0