🚀 go-pugleaf

"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