3-partition problem: Difference between revisions

Revision as of 07:07, 26 April 2023

Revision as of 19:38, 10 December 2023

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 isInput: a multiset ''S'' ofcontaining ''n'' = 3{{hsp|''m''}} positive integers. The sum of all integers is {{tmath|minteger T}}elements.

* The output is whether or not there exists a partition ofConditions: ''S'' must be partitionable into ''m'' triplets, ''S''₁, ''S''₂, …, ''S''_''m'', such that the sum of the numbers in each one is equal towhere ''T''.n The= 3m''S''₁,. ''S''₂, …,These ''S''_''m'' must form atriplets [[Partition of a set|partition]] of ''S'' in the sense that they are [[Disjoint sets|disjoint]] and they [[Cover (topology)|cover]] ''S''. The target value ''T'' is computed by taking the sum of all elements in ''S'', then divided by ''m''.

* Output: whether or not there exists a partition of ''S'' such that, for all triplets, the sum of the elements in each triplet equals ''T''.

The 3-partition problem remains strongly NP-complete under the restriction that every integer in ''S'' is strictly between ''T''/4 and ''T''/2.