3-partition problem: Difference between revisions

Revision as of 08:58, 2 February 2024

Latest revision as of 12:19, 6 August 2025

(14 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|Strongly NP-complete problem in computer science}}

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:

* Input: a multiset ''S'' containing ''n'' positive integer elements.

* Conditions: ''S'' must be partitionable into ''m'' triplets, ''S''₁, ''S''₂, …..., ''S''_''m'', where ''n = 3m''. These triplets [[Partition of a set|partition]] ''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 divideddividing 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''.

Line 23 ⟶ 24:

==Variants==

In the '''unrestricted-input variant''', the inputs can be arbitrary integers; in the '''restricted-input variant''', the inputs must be in (''T''/4'', T''/2). The restricted version is as hard as the unrestricted version: given an instance ''S_u'' of the unrestricted variant, construct a new instance of the restricted version {{math|''S_r'' ≔ {s + 2{{hsp|''T''}} {{!}} s ∈ ''S_u''}}}. Every solution of ''S_u'' corresponds to a solution of ''S_r'' but with a sum of 7{{hsp|''T''}} instead of ''T'', and every element of ''S_r'' is in {{nowrap|[2{{hsp|''T''}}, 3{{hsp|''T''}}]}} which is contained in {{nowrap|{{pars|7{{hsp|''T''}}/4, 7{{hsp|''T''}}/2}}}}.

In the '''distinct-input variant''', the inputs must be in (''T''/4'', T''/2), and in addition, they must all be distinct integers. It, too, is as hard as the unrestricted version.<ref>{{Cite journal|last1=Hulett|first1=Heather|last2=Will|first2=Todd G.|last3=Woeginger|first3=Gerhard J.|date=2008-09-01|title=Multigraph realizations of degree sequences: Maximization is easy, minimization is hard|url=http://www.sciencedirect.com/science/article/pii/S0167637708000552|journal=Operations Research Letters|language=en|volume=36|issue=5|pages=594–596|doi=10.1016/j.orl.2008.05.004|issn=0167-6377|url-access=subscription}}</ref>

In the '''unrestricted-output variant''', the ''m'' output subsets can be of arbitrary size - not necessarily 3 (but they still need to have the same sum ''T''). The restricted-output variant can be reduced to the unrestricted-variant: given an instance ''S_r'' of the restricted variant, with 3''m'' items summing up to ''mT'', construct a new instance of the unrestricted variant {{math|''S_u'' ≔ {s + 2''T'' {{!}} s &isin; ''S_r''}}}, with 3m items summing up to 7mT, and with target sum 7{{hsp|''T''}}. Every solution of ''S_r'' naturally corresponds to a solution of ''S_u''. Conversely, in every solution of ''S_u'', since the target sum is 7{{hsp|''T''}} and each element is in {{nowrap|{{pars|7{{hsp|''T''}}/4, 7{{hsp|''T''}}/2}}}}, there must be exactly 3 elements per set, so it corresponds to a solution of ''S_r''.

The '''4ABC-partition problem''' (also called '''[[Numerical 3-dimensional matching|numerical 3-d matching]])''' is a variant in which, ''S''instead containsof a set ''nS'' =with 43{{hsp|''m''}} integers, thethere are three sets ''A'', ''B'', ''C'' with ''m'' integers in each. The sum of numbers in all integerssets is {{tmath|m T}},. and theThe goal is to partition it intoconstruct ''m'' quadrupletstriplets, alleach withof awhich contains one element from A, one from B and one from C, such that the sum of each triplet is ''T''.<ref>{{Cite Itweb|last=Demaine|first=Erik|date=2015|title=MIT canOpenCourseWare be- assumedHardness thatmade eachEasy integer2 is- strictly between3-Partition ''T''I|url=https:/5/www.youtube.com/watch?v=ZaSMm2xvatw and ''T''|archive-url=https:/3/ghostarchive.org/varchive/youtube/20211214/ZaSMm2xvatw |archive-date=2021-12-14 |url-status=live|website=Youtube}}{{cbignore}}</ref>

The '''4-partition problem''' is a variant in which ''S'' contains ''n'' = 4{{hsp|''m''}} integers, the sum of all integers is {{tmath|m T}}, and the goal is to partition it into ''m'' quadruplets, all with a sum of ''T''. It can be assumed that each integer is strictly between ''T''/5 and ''T''/3. Similarly, '''ABCD-partition''' is a variant of 4-partition in which there are 4 input sets and each quadruplet should contain one element from each set.

The '''ABC-partition problem''' is a variant in which, instead of a set ''S'' with 3{{hsp|''m''}} integers, there are three sets ''A'', ''B'', ''C'' with ''m'' integers in each. The sum of numbers in all sets is {{tmath|m T}}. The goal is to construct ''m'' triplets, each of which contains one element from A, one from B and one from C, such that the sum of each triplet is ''T''. <ref>{{Cite web|last=Demaine|first=Erik|date=2015|title=MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I|url=https://www.youtube.com/watch?v=ZaSMm2xvatw |archive-url=https://ghostarchive.org/varchive/youtube/20211214/ZaSMm2xvatw |archive-date=2021-12-14 |url-status=live|website=Youtube}}{{cbignore}}</ref> This problem can be reduced to 3-partition as follows. Construct a set S containing the numbers {{gaps|1000''a''|+|100}} for each {{tmath|a \in A}}; {{gaps|1000''b''|+|10}} for each {{tmath|b \in B}}; and {{gaps|1000''c''|+|1}} for each {{tmath|c \in C}}. Every solution of the ABC-partition instance induces a solution of the 3-partition instance with sum <math>1000(a+b+c)+111 = 1000T+111</math>. Conversely, in every solution of the 3-partition instance, all triplet-sums must have the same hundreds, tens and units digits, which means that they must have exactly 1 in each of these digits. Therefore, each triplet must have exactly one number of the form {{gaps|1000''a''|+|100}}, one {{gaps|1000''b''|+|10}} and one {{gaps|1000''c''|+|1}}. Hence, it induces a solution to the ABC-partition instance.

* The ABC-partition problem is also called '''[[Numerical 3-dimensional matching|numerical 3-d matching]]''', as it can also be reduced to the [[3-dimensional matching]] problem: given an instance of ABC-partition, construct a tripartite hypergraph with sides {{tmath|A, B, C}}, where there is an hyperedge {{tmath|(a, b, c)}} for every three vertices in {{tmath|A, B, C}} such that <math>a+b+c = T</math>. A matching in this hypergraph corresponds to a solution to ABC-partition.

Similarly, '''ABCD-parititon''' is a variant of 4-partition in which each there are 4 input sets and each quadruplet should contain one element from each set.

== Proofs ==

Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from [[3-dimensional matching]].<ref>{{cite journal|author=[[Michael Garey|Garey, Michael R.]] and [[David S. Johnson]]|year=1975|title=Complexity (1979),results ''Computersfor andmultiprocessor Intractability;scheduling Aunder Guideresource toconstraints|journal=SIAM theJournal Theoryon of NP-Completeness''Computing|volume=4|issue=4|pages=397–411|doi=10. {{ISBN|0-7167-1045-51137/0204035}}. Pages 96–105 and 224.</ref> The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition.<ref>{{cite journal|author=[[Michael Garey|Garey, Michael R.]] and [[David S. Johnson]]|year=1975|title=Complexity results(1979), for''Computers multiprocessorand schedulingIntractability; underA resourceGuide constraints|journal=SIAMto Journalthe onTheory Computing|volume=4|issue=4|pages=397–411|doi=10of NP-Completeness''.1137/0204035 {{ISBN|0-7167-1045-5}}. Pages 96–105 and 224.</ref> Logically, the reduction can be partitioned into several steps.

=== Reduction from 3d-matching to ABCD-partition ===

We are given an instance of E of 3d-matching, containing some ''m'' triplets {w_i,x_j,y_k}, where the vertices are w₁,...,w_q and x₁,...,x_q and y₁,...,y_q. We construct an instance of ABCD-partition with 4*''m'' elements, as follows (where r := 32q):

* For each triplet t = {w_i,x_j,y_k} in E, the set A contains an element u_t = 10r⁴-kr³-jr²-ir.

* For each triplet t = {w_i,x_j,y_k} in E, the set B contains w_it, C contains x_jt, and D contains y_kt. So for each of w_i, x_j, y_k, there may be many corresponding elements in B, C, D - one for each triplet in which they appear. We consider one of these elements (denoted by "1") as the "real" one, and the others as "dummy" ones. The element sizes are as follows:

** w_i[1] = 10r⁴+ir; w_i[2+..] = 11r⁴+ir.

** x_j[1] = 10r⁴+jr²; x_j[2+..] = 11r⁴+jr².

** y_k[1] = 10r⁴+kr³; y_k[2+..] = 8r⁴+kr³.

* The sum of every three "real" elements or every three "dummy" elements is 30r⁴+ir+jr²+kr³; and ofif the triplet element is added, the sum is 40r⁴.

* The threshold for the ABCD-partition instance is T=40r⁴. Note that the size of each element is in (T/3,T/5).

Line 72 ⟶ 70:

Every ABCD-partition corresponds naturally to a 4-partition. Conversely, in every 4-partition, the sum modulo 16 is 15, and therefore it must contain exactly one item with size modulo 16 = 1, 2, 4, 8; this corresponds to exactly one item from A, B, C, D, from which we can construct an ABCD-partition.

===Using Reductiona fromsimilar 3dreduction, ABC-matchingpartition can be reduced to 43-partition ===.

We are given an instance of E of 3d-matching, containing some ''m'' triplets {w_i,x_j,y_k}, where the vertices are w₁,...,w_q and x₁,...,x_q and y₁,...,y_q. We construct an instance A of 4-partition as follows (where r := 32q):

* For each triplet t = {w_i,x_j,y_k} in E, A contains an element u_t = 10r⁴-kr³-jr²-ir+8.

* For each triplet t = {w_i,x_j,y_k} in E, A contains elements w_it, x_jt, y_kt. So for each of w_i, x_j, y_k, there may be many corresponding elements in A - one for each triplet in which they appear. We consider one of these elements (denoted by "1") as the "real" one, and the others as "dummy" ones. The element sizes are as follows:

** w_i[1] = 10r⁴+ir+1; w_i[2+] = 11r⁴+ir+1.

** x_j[1] = 10r⁴+jr²+2; x_j[2+] = 11r⁴+jr²+2.

** y_k[1] = 10r⁴+kr³+4; y_k[2+] = 8r⁴+kr³+4.

* The sum of every three "real" elements or every three "dummy" elements is 30r⁴+ir+jr²+kr³+7; and of the triplet element is added, the sum is 40r⁴+15.

* The threshold for the 4-partition instance is T=40r⁴+15. Note that the size of each element is in (T/3,T/5).

Given a perfect matching in ''E'', we construct a 4-partition of A as follows:

* For each triplet ''t='' {''w_i,x_j,y_k''} in the matching, we construct a 4-set {u_t, w_i[1], x_j[1], y_k[1]}.

* For each triplet not in the matching, we construct a similar 4-set, but with the dummy elements.

In both cases, the sum of the 4-set is 40r⁴+15 as needed.

Given a 4-partition of A, the sum of each 4-set is 40r⁴+15, and therefore it must contain elements whose size ends with +1, +2, +4, +8; that is, three vertex-elements and one triplet-element. Moreover, the terms with r, r² and r³ must cancel out, and the terms with r⁴ must sum up to 40r⁴; therefore, the 4-set must contain a triplet and 3 matching "real" elements, or a triplet and 3 matching "dummy" elements. From the triplets with the 3 matching "real" elements, we construct a valid perfect matching in E.

Note that, in the above reduction, the size of each element is polynomial in the input size; hence, this reduction shows that 4-partition is ''strongly'' NP-hard.

=== Reduction from 4-partition to 3-partition ===

Line 114 ⟶ 92:

== Applications ==

The NP-hardness of 3-partition was used to prove the NP-hardness [[rectangle packing]], as well as of [[Tetris#Computational complexity|Tetris]]<ref>{{Cite journal|date=2002-10-28|title=Tetris is hard, even to approximate|url=http://dx.doi.org/10.1038/news021021-9|journal=Nature|doi=10.1038/news021021-9|issn=0028-0836|url-access=subscription}}</ref><ref>{{Cite journal|last1=BREUKELAAR|first1=RON|last2=DEMAINE|first2=ERIK D.|last3=HOHENBERGER|first3=SUSAN|last4=HOOGEBOOM|first4=HENDRIK JAN|last5=KOSTERS|first5=WALTER A.|last6=LIBEN-NOWELL|first6=DAVID|title=Tetris is Hard, Even to Approximate|date=2004-04-01|url=http://dx.doi.org/10.1142/s0218195904001354|journal=International Journal of Computational Geometry & Applications|volume=14|issue=1n02|pages=41–68|doi=10.1142/s0218195904001354|issn=0218-1959|arxiv=cs/0210020|s2cid=1177 }}</ref> and some other puzzles,<ref>{{Cite journal|last1=Demaine|first1=Erik D.|last2=Demaine|first2=Martin L.|date=2007-06-01|title=Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity|url=http://dx.doi.org/10.1007/s00373-007-0713-4|journal=Graphs and Combinatorics|volume=23|issue=S1|pages=195–208|doi=10.1007/s00373-007-0713-4|s2cid=17190810 |issn=0911-0119|url-access=subscription}}</ref> and some [[Job scheduling|job scheduling problems]].<ref>{{Cite journal|last1=Bernstein|first1=D.|last2=Rodeh|first2=M.|last3=Gertner|first3=I.|date=1989|title=On the complexity of scheduling problems for parallel/pipelined machines|url=http://dx.doi.org/10.1109/12.29469|journal=IEEE Transactions on Computers|volume=38|issue=9|pages=1308–1313|doi=10.1109/12.29469|issn=0018-9340|url-access=subscription}}</ref>

==References==