3-Partition Problem

computation scheduling

Definition

3-Partition Problem

The 3-partition problem is a strongly NP-hard decision problem that asks whether a multiset of positive integers can be partitioned into triplets with equal sum.

Instance: a multiset of positive integers, where .
Question: can be partitioned into sets such that

where

Relation

The 3-partition problem is a specialised k-partition problem. Here the number of parts is , and each part must contain exactly three integers.

First compute the target sum per part. Since all integers must be used and there must be equal-sum parts, each part must have sum

Thus is not an additional input value. It is the only possible sum of each part if an equal partition exists.

The standard hard version restricts every integer to lie strictly between one quarter and one half of this target:

These bounds force the number of integers in each part.

One integer cannot form a part, because every integer is smaller than .

Two integers cannot form a part either. If , then

So one or two integers are always too small to reach the required part sum .

Four integers cannot form a part. If , then

So four integers are already too large, and any larger group is too large as well.

A valid part must therefore contain neither fewer than three nor more than three integers. It must contain exactly three integers. This is why the equal-sum condition plus the bounds already force triplets.

Strong NP-Hardness

3-partition is strongly NP-hard, even under the restriction

This makes 3-partition useful for reductions to scheduling problems. The bounds force each target block of size to contain exactly three jobs or items, so the reduction can encode grouping rather than only numerical summation.