# Reduction from PARTITION to 3PARTITION

I'm considering the problem (a variant of 3-PARTITION, see here) with description

Instance: Set of positive integers $A={w_{1},...,w_{n}}$ with $S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$.
Question: Is there a partition of $A$ into 3 subsets $A=A_{1}\cup A_{2}\cup A_{3}$ such that $S(A_{1})=S(A_{2})=S(A_{3})$?

I plan to give a reduction from simple PARTITION (into two subsets with equal sum) to this problem that is going like this.

a) Observe that if there is no $A'\subset A$ with $S(A')=2m/3$ then $A$ can't be partitioned into 3 subsets with sum equal to m. (because the premise implies that there's also no subset of A with sum equal to m).

b) Build an instance for PARTITION by taking a subset $A'$ of A with $S(A')=2m/3$. If it is a correct instance of PARTITION then it can be partitioned into sets $B,C$ which combined with $A\setminus A'$ produce a correct instance for the problem 3PARTITION. The other way round (correct instance for 3PARTITION -->correct instance for PARTITION) can be proved by equally simple arguments.

Is this reduction polynomial? I mean, the choice of $A'$ is arbitrary and itself is a correct instance for the problem of SUBSET-SUM for A with target value equal to $2m/3$ which is hard to compute. If this computation plays a part in the transformation then the latter can't be polynomial, right?

• It might be polynomial (if P=NP), but we don't know. You haven't given an algorithm for finding $A'$, so it's hard to tell. – Yuval Filmus Feb 5 '17 at 15:13

$A=w_1,...,w_n$ with $S(A)=\sum\limits^{n}_{i=1}w_{i}=2m$
ii) Append $m$ to $A$ and obtain $A'$, an instance of the 3PARTITION problem.
iii) Prove that $A\in PARTITION\Longleftrightarrow A'\in 3PARTITION$
iv) Conclude that $PARTITION \leq_{p}3PARTITION$