Content deleted Content added
Erel Segal (talk | contribs) →Variants: Thanks to Juho https://cs.stackexchange.com/a/60320/1342 |
Erel Segal (talk | contribs) No edit summary Tags: nowiki added Visual edit |
||
Line 31:
== Proofs ==
Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from [[3-dimensional matching]].<ref>[[Michael Garey|Garey, Michael R.]] and [[David S. Johnson]] (1979), ''Computers and Intractability; A Guide to the Theory of NP-Completeness''. {{ISBN|0-7167-1045-5}}. 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 for multiprocessor scheduling under resource constraints|journal=SIAM Journal on Computing|volume=4|issue=4|pages=397–411|doi=10.1137/0204035}}</ref>
== Applications ==
The NP-hardness of 3-partition was used to prove the NP-hardness 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|last=BREUKELAAR|first=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|date=2004-04-01|title=TETRIS IS HARD, EVEN TO APPROXIMATE|url=http://dx.doi.org/10.1142/s0218195904001354|journal=International Journal of Computational Geometry & Applications|volume=14|issue=01n02|pages=41–68|doi=10.1142/s0218195904001354|issn=0218-1959|via=}}</ref> as well as of some [[Job scheduling|job scheduling problem]]<nowiki/>s.<ref>{{Cite journal|last=Bernstein|first=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}}</ref>
==References==
| |||