Content deleted Content added
m Task 18 (cosmetic): eval 7 templates: del empty params (5×); del |url-status= (1×); |
Citation bot (talk | contribs) Alter: title, issue. Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform |
||
Line 21:
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<sub>u</sub>'' of the unrestricted variant, construct a new instance of the restricted version ''S<sub>r</sub>'' := {s + 2 ''T'' | s in ''S<sub>u</sub>''}. Every solution of ''S<sub>u</sub>'' corresponds to a solution of ''S<sub>r</sub>'' but with a sum of 7 ''T'' instead of ''T'', and every element of ''S<sub>r</sub>'' is in [2 ''T'', 3 ''T''] which is contained in (7 ''T'' / 4, 7 ''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|
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<sub>u</sub>'' of the restricted variant, construct a new instance of the unrestricted variant ''S<sub>r</sub>'' := {s + 2 ''T'' | s in ''S<sub>u</sub>''}, with target sum 7 ''T''. Every solution of ''S<sub>u</sub>'' naturally corresponds to a solution of ''S<sub>r</sub>''. In every solution of ''S<sub>r</sub>'', since the target sum is 7 ''T'' and each element is in (7 ''T'' / 4, 7 ''T'' / 2), there must be exactly 3 elements per set, so it corresponds to a solution of ''S<sub>u</sub>''.
Line 27:
The '''4-partition problem''' is a variant in which ''S'' contains ''n'' = 4 ''m'' integers, the sum of all integers is ''m T'', and the goal is to partition it into ''m'' quadruples, all with a sum of ''T''. It can be assumed that each integer is strictly between ''T''/5 and ''T''/3.
The '''ABC-partition problem''' is a variant in which, instead of a set ''S'' with 3 ''m'' integers, there are three sets ''A'', ''B'', ''C'' with ''m'' integers in each. The sum of numbers in all sets is ''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 -
* 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 A, B, C, where there is an hyperedge (a, b, c) for every three vertices in A, B, C such that a+b+c = ''T''. A matching in this hypergraph corresponds to a solution to ABC-partition.
Line 35:
== Applications ==
The NP-hardness of 3-partition was used to prove the NP-hardness [[rectangle packing]], as well as of [[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}}</ref><ref>{{Cite journal|
==References==
| |||