Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!wisdom.weizmann.ac.IL!harel From: harel@wisdom.weizmann.ac.IL (David Harel) Newsgroups: comp.theory Subject: Re: Monkeys are NP-complete Message-ID: <9002040639.AA02014@peres.wisdom.weizmann.ac.il> Date: 8 Feb 90 14:49:09 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: David Harel Lines: 20 "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