Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
3-partition problem
open-in-new
<p>The 3-partition problem is a <a href="/facts/Strong_NP-completeness/rqFp8pxx">strongly NP-complete</a> problem in <a href="/facts/Computer_science/lN3pEyPz">computer science</a>. The problem is to decide whether a given <a href="/facts/Multiset/bPFJGMDo">multiset</a> of integers can be partitioned into triplets that all have the same sum. More precisely: </p> <ul><li>Input: a multiset <i>S</i> containing <i>n</i> positive integer elements.</li> <li>Conditions: <i>S</i> must be partitionable into <i>m</i> triplets, <i>S</i>1, <i>S</i>2, …, <i>S</i><i>m</i>, where <i>n = 3m</i>. These triplets <a href="/facts/Partition_of_a_set/VeP9g8CA">partition</a> <i>S</i> in the sense that they are <a href="/facts/Disjoint_sets/nLr8XRVd">disjoint</a> and they <a href="/facts/Cover_(topology)/2VUdelA4">cover</a> <i>S</i>. The target value <i>T</i> is computed by taking the sum of all elements in <i>S</i>, then divided by <i>m</i>.</li> <li>Output: whether or not there exists a partition of <i>S</i> such that, for all triplets, the sum of the elements in each triplet equals <i>T</i>.</li></ul> <p>The 3-partition problem remains strongly NP-complete under the restriction that every integer in <i>S</i> is strictly between <i>T</i>/4 and <i>T</i>/2. </p>