3-partition problem: Difference between revisions

Revision as of 23:15, 23 May 2025

Latest revision as of 12:19, 6 August 2025

(2 intermediate revisions by 2 users not shown)

Line 3:

* 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 dividing 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 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 '''ABC-partition problem''' (also called '''[[Numerical 3-dimensional matching|numerical 3-d matching]])''' 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>

Line 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==