harel@wisdom.weizmann.ac.IL (David Harel) (02/13/90)
I would like to clear up the issue of the NP-completeness of the monkey-puzzle problem. The problem appeared on pages 153-155 of "Algorithmics: The Spirit of Computing", Addison-Wesley, 1987, where it used as an example of an NP-complete problem. It is a generalized version of the well-known problem involving 9 cards with tops and bottoms of colored monkeys (or elephants, or whatever), which have to be arranged in a square of size 3x3, such that colors and monkey-halves match. A less zoological version is this: INPUT: a set of n^2 square tiles, each colored at the edges, and each with a fixed orientation (although this last restriction is not important). Colors are paired, and tiling must adhere to the pairing, in the sense that adjacent edges must be colored with matching colors. OUTPUT: "yes" iff these very n^2 tiles can be arranged in a legal nxn square. There followed a spree of email, started with a query by Anne Lomax on TheoryNet The main issue was whether or not this was simply the standard tiling problem, well known to be NP-complete (Levin 1973, Garey, Johnson and Papadimitriou 1977, Lewis 1978). It clearly isn't that problem exactly, since here you have to use exactly the n^2 given tiles, whereas in the standard problem you are given a set of tile TYPES and a number n, and the tiling of the nxn square is to be done using tiles from among the given set. The proof I had in mind when using the problem in the book is the following, inspired by a discussion with Adi Shamir: PROOF#1: The reduction is from 3-PARTITION (Garey and Johnson, p. 224), which is NP-complete in the strong sense. Given the 3m numbers and the bound B that form an input to 3-PARTITION, prepare a set of cards for each number, that make it possible to tile the tiles in this set side by side only. Hence,if the number is say, 17, there will be 17 cards that can only fit together to form a line of length 17. Each of these tile lines has colors to enable it to be attached on either end to any 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. It now helps to assume that m>B (the proof can be easily modified to cover the more general case). Now, prepare a set of m(m-B) tiles of a special kind, that enable ONLY a tiling of a rectangle of width m-B and height 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 tile an mxm square if and only if the 3m numbers can be partitionied into m triplets, each summing to B. In an email exchange with Leonid Levin, he showed that, in fact, the difference between this version of tiling and the usual does not cause much of a problem, and one can use the latter for the reduction. Here is his proof: PROOF#2: Since the regular tiling problem is is NP-complete even with a fixed, constant number of tiles, the reduction can be carried out as follows. Given k tiles and n (in unary), and having to say whether they can be used to tile an nxn square, proceed by submitting to the monkey-puzzle problem all possibilities of preparing sets of n^2 tiles from among the given k tile types. Since each of these k tile types can appear at most n^2 times, there is a bound of n^(2xk) on the number of monkey-puzzle problems you must try. Hence the reduction is polynomial.