1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 5 '17 at 15:13
0
$\begingroup$

I guess that this question should not be left floating around unanswered.

The reasoning in (b) can't be used to prove that this problem is NP-complete because, at best, it implies the reduction from 3PARTITION to PARTITION which is of no use. Any problem in NP can be reduced to PARTITION.

The proper way of doing this (after showing that the problem is in NP) is to:
i) Start from an arbitrary instance of PARTITION
$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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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