🚀 go-pugleaf

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