Content deleted Content added
No edit summary |
|||
Line 1:
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'' [[Tuple|triplets]] ''S''<sub>1</sub>, ''S''<sub>2</sub>, …, ''S''<sub>''m''</sub> such that the sum of the numbers in each subset is equal? The subsets ''S''<sub>1</sub>, ''S''<sub>2</sub>, …, ''S''<sub>''m''</sub> must form a [[Partition of a set|partition]] of ''S'' in the sense that they are [[Disjoint sets|disjoint]] and they [[Cover (topology)|cover]] ''S''. Let ''B'' denote the (desired) sum of each subset ''S''<sub>''i''</sub>, 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.
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 two subsets, with equal sum.
| |||