3-partition problem

The 3-partition problem is an NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset "S" of "n" = 3 "m" positive integers, can "S" be partitioned into "m" subsets "S"₁, "S"₂, …, "S"_"m" such that the sum of the numbers in each subset is equal? The subsets "S"₁, "S"₂, …, "S"_"m" must form a partition of "S" in the sense that they are disjoint and they cover "S". Let "B" denote the (desired) sum of each subset "S"_"i", or equivalently, let the total sum of the numbers in "S" be "m" "B". The 3-partition problem remains NP-complete when every integer in "S" is strictly between "B"/4 and "B"/2. In this case, each subset "S"_"i" is forced to consist of exactly three elements (a triple).

The 3-partition problem is similar to the partition problem, which in turn is related to the subset sum problem. In the partition problem, the goal is to partition "S" into two subsets with equal sum. It is important to note that in 3-partition the goal is to partition "S" into "m" subsets (or "n"/3 subsets), not just three subsets, with equal sum.

trong NP-completeness

What is interesting about 3-partition is that it remains NP-complete even when the integers in "S" are bounded above by a polynomial in "n". In other words, the problem remains NP-complete even when representing the numbers in the input instance in unary. In other words, 3-partition is NP-complete in the strong sense or strongly NP-complete. This property, and 3-partition in general, is useful in many reductions where numbers are naturally represented in unary. In contrast, the partition problem is known to be NP-complete only when the numbers are encoded in binary, and have value exponential in "n".

Descriptions

Garey and Johnson (1975) originally proved that 3-partition to be NP-complete, by a reduction from 3-dimensional matching. The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition. The 4-partition problem is an analog of 3-partition in which the goal is to partition a given set "S" into quadruples all with the same sum: precisely, the difference is that "S" now consists of "n" = 4 "m" integers, each strictly between "B"/5 and "B"/3.

References

* Garey, Michael R. and David S. Johnson (1979), "Computers and Intractability; A Guide to the Theory of NP-Completeness". ISBN 0-7167-1045-5. Pages 96–105 and 224.

*