# a direct polynomial reduction from 3EQU-SUM to EQU-SUM problem [closed]

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?

• 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$. May 29, 2020 at 7:58