Content deleted Content added
m corrected the problem definition |
m Changed a three to a two since here referring to the partition problem (which goal is to partition into two subsets) |
||
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'' [[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. In this case, each subset ''S''<sub>''i''</sub> 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
==Strong NP-completeness==
| |||