Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!wuarchive!psuvax1!shire!berman From: berman@shire.cs.psu.edu (Piotr Berman) Newsgroups: comp.theory Subject: Re: Monkeys are NP-complete Message-ID: Date: 9 Feb 90 16:45:31 GMT References: <9002040639.AA02014@peres.wisdom.weizmann.ac.il> Sender: news@cs.psu.edu (Usenet) Organization: Penn State University Computer Science Lines: 29 In article <9002040639.AA02014@peres.wisdom.weizmann.ac.il> David Harel 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