11.15

Reduction from PARTITION
Given an instance of PARTITION we are handed a multiset [math]\displaystyle{ S=\{s_1,\dots ,s_m\} }[/math] of positive integers. Let [math]\displaystyle{ T=\sum_{i=1}^{m}s_i }[/math]. PARTITION asks whether there is a subset whose elements add up to [math]\displaystyle{ T/2 }[/math]. (If T is odd the answer is instantly “no”, so we assume T is even.)

Constructing the 3-phase instance
Add one extra number
[math]\displaystyle{ y=T/2 }[/math]
and keep every element of S. The new multiset is
[math]\displaystyle{ S' = S \cup \{y\}. }[/math] Its total sum is
[math]\displaystyle{ T' = T + y = 3T/2. }[/math] Therefore each of the three target phase-sums must equal
[math]\displaystyle{ T'/3 = T/2. }[/math]

Equivalence of solutions
• If the PARTITION instance is solvable, split S into two disjoint sets A and B that each sum to T/2. Let C = {y}. Then
[math]\displaystyle{ \sum_{a\in A}a=\sum_{b\in B}b=\sum_{c\in C}c=T/2, }[/math] so ⟨A,B,C⟩ is a feasible 3-phase solution.
• Conversely, suppose ⟨A,B,C⟩ is a feasible 3-phase solution for S′. Because y = T/2, exactly one of the three sets must contain y (otherwise some set would exceed T/2). Remove y and call the remaining two sets A′ and B′; they partition the original multiset S and each sums to T/2, giving a solution to PARTITION.

Complexity
The reduction adds exactly one integer and performs O(m) arithmetic, i.e. it is polynomial-time. Since PARTITION is NP-complete, this many-one reduction shows that the 3-phase power-balance problem is NP-hard. (Membership in NP is immediate because a proposed tripartition can be verified by three additions.)

Back to Chapter 11