harel@wisdom.weizmann.ac.IL (David Harel) (02/03/90)
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.
harel@wisdom.weizmann.ac.IL (David Harel) (02/08/90)
"David,
NP-completeness of Tiling (or, as you call it, Monkey problem) is given in my
1973 paper. To prove it just consider straightforwardly the space-time history
of the computation of a Universal Turing Machine, verifying the witness of an
arbitrary NP-problem. Tiling is even complete for an "average" instance, while
most other problems are only "worst-case NP-complete".
Yours, Leonid Levin."
Hi Leonid,
I know about your proof of the tiling problem. It is NOT the same as the
monkey problem, not because we have monkeys instead of colored tiles, but
because we are given a FULL set of n^2 tiles and we have to use them ALL
exactly once. The reductions from computations of TMs use a fixed set
of tiles constructed from the TM and used (possibly only some of them)
more than once. The case where you have the full set and have to use them
all exactly once cannot, I think, be proved in this way. Hence the need for
a different proof. I hope you see easily that this is needed.
Davidberman@shire.cs.psu.edu (Piotr Berman) (02/10/90)
In article <9002040639.AA02014@peres.wisdom.weizmann.ac.il> David Harel <harel%wisdom.weizmann.ac.il@VM1.NoDak.EDU> writes: >"David, >NP-completeness of Tiling (or, as you call it, Monkey problem) is given in my >1973 paper. To prove it just consider straightforwardly the space-time history >of the computation of a Universal Turing Machine, verifying the witness of an >arbitrary NP-problem. Tiling is even complete for an "average" instance, while >most other problems are only "worst-case NP-complete". > Yours, Leonid Levin." > >Hi Leonid, > >I know about your proof of the tiling problem. It is NOT the same as the >monkey problem, not because we have monkeys instead of colored tiles, but >because we are given a FULL set of n^2 tiles and we have to use them ALL >exactly once. The reductions from computations of TMs use a fixed set >of tiles constructed from the TM and used (possibly only some of them) >more than once. The case where you have the full set and have to use them >all exactly once cannot, I think, be proved in this way. Hence the need for >a different proof. I hope you see easily that this is needed. > >David One should also notice that there are only two monkeys on each card. I tried to reconstruct the reduction from Hamiltonian Path and given a graph with n veritices and e edges, I used roughly e^2 cards, such large description of the reduction result suggests that this problem is not complete on average. Piotr