Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!sun-barr!decwrl!ucbvax!wisdom.weizmann.ac.IL!harel From: harel@wisdom.weizmann.ac.IL (David Harel) Newsgroups: comp.theory Subject: Monkeys are NP-complete Message-ID: <9002020816.AA00683@peres.wisdom.weizmann.ac.il> Date: 3 Feb 90 07:35:56 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: David Harel Lines: 28 Monkey puzzle is NP-complete: In response to the query of Anne Lomax on TheoryNet, Feb. 1, 1990. ----------------------------------------------------------------------- You are right -- I did not include a pointer to the proof in the bibliographic notes of the Algorithmics book. The idea is inspired by a discussion I had with Adi Shamir. The reduction is from 3-PARTITION, which is NP-complete in the strong sense (see Garey and Johnson's book, page 224). Given the 3m numbers, you prepare a set of cards for each, that make it possible to tile the tiles in the set side by side only. So if the number is, say, 17, there will be 17 cards that can only fit together to form a line of length 17, but they have colors (or monkey halves) to enable that line to be attached on either side to some other such line. In addition, each line is colored on the top and bottom to enable attachment to other such lines from above and below. Now, you prepare a set of m^2-3m tiles of a special kind, that enable ONLY a tiling of a rectangle of width m-3 and heght m, whose left hand side can be attached to the ends of the lines coming from the numbers. It can now be shown that these tiles can cover an mxm square if and only if you can partition the 3m numbers into m triplets, each summing to B. For one direction, if the numbers can be partitioned so, then you would lay down m lines of tiles, each representing the three numbers in the triplet, and each then being of total length B, and the rest of the square would then be a rectangle as above, and tiled with the extra tiles. Conversely, assume you have been able to make the mxm square. Then, the fact that you have managed to lay down the (m-3)xm rectangle means that the rest of the square is a rectangle too, and since each number is between B/2 and B/4, there must be exactly three numbers per line, hence you have your partition.