3-partition problem: Difference between revisions

Revision as of 17:19, 16 November 2022

Revision as of 17:23, 16 November 2022

Line 1:

The '''3-partition problem''' is a [[Strong NP-completeness|strongly NP-complete]] problem in [[computer science]]. The problem is to decide whether a given [[multiset]] of integers can be partitioned into triplets that all have the same sum. More precisely:

* The input to the problem is a multiset ''S'' of ''n'' = 3 {{hsp|''m''}} positive integers. The sum of all integers is ''{{tmath|m T''}}.

* The output is whether or not there exists a partition of ''S'' into ''m'' triplets ''S''₁, ''S''₂, …, ''S''_''m'' such that the sum of the numbers in each one is equal to ''T''. The ''S''₁, ''S''₂, …, ''S''_''m'' 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''.

Line 8:

==Example==

# The set {{<math|1=''>S'' = \{{mset| 20, 23, 25, 30, 49, 45, 27, 30, 30, 40, 22, 19 \}}}}</math> can be partitioned into the four sets {{<math|{>\{mset| 20, 25, 45 }\}, \{{mset| 23, 27, 40 }\}, \{{mset| 49, 22, 19 }\} , \{{mset| 30, 30, 30\}}}}</math>, each of which sums to ''T'' = 90.

# The set {{<math|1=''>S'' = \{{mset|1, 2, 5, 6, 7, 9\}}}}<math> can be partitioned into the two sets {{<math|{>\{mset|1, 5, 9}\}, \{{mset|2, 6, 7\}}}}</math> each of which sum to ''T'' = 15.

# (every integer in ''S'' is strictly between ''T''/4 and ''T''/2): {{<math|1=''>S'' = \{{mset|4,5,5,5,5,6\}}}}</math>, thus ''m''=2, and ''T''=15. There is feasible 3-partition {{<math|>\{{mset|4,5,6}\}, \{{mset|5,5,5\}}}}</math>.

# (every integer in ''S'' is strictly between ''T''/4 and ''T''/2): {{<math|1=''>S'' = \{{mset|4,4,4,6,6,6\}}}}</math>, thus ''m''=2, and ''T''=15. There is no feasible solution.

==Strong NP-completeness==