3-partition problem
Encyclopedia
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 S1, S2, …, Sm such that the sum of the numbers in each subset is equal? The subsets S1, S2, …, Sm 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 Si, 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 Si 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. In 3-partition the goal is to partition S into m subsets (or n/3 subsets), not just three subsets, with equal sum.
. 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.
. 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.
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. The problem is to decide whether a given multiset
Multiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
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 S1, S2, …, Sm such that the sum of the numbers in each subset is equal? The subsets S1, S2, …, Sm must form a partition
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
of S in the sense that they are disjoint and they cover
Cover (topology)
In mathematics, a cover of a set X is a collection of sets whose union contains X as a subset. Formally, ifC = \lbrace U_\alpha: \alpha \in A\rbrace...
S. Let B denote the (desired) sum of each subset Si, 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 Si is forced to consist of exactly three elements (a triple).
The 3-partition problem is similar to the partition problem
Partition problem
In computer science, the partition problem is an NP-complete problem. The problem is to decide whether a given multiset of integers can be partitioned into two "halves" that have the same sum...
, 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. In 3-partition the goal is to partition S into m subsets (or n/3 subsets), not just three subsets, with equal sum.
Strong NP-completeness
The 3-partition problem 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. i.e., 3-partition is NP-complete in the strong sense or strongly NP-completeStrongly NP-complete
In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters...
. 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 matching3-dimensional matching
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-uniform hypergraphs...
. 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.