At 4:29 PM 9/23/96, Asgaard wrote:
On Sun, 22 Sep 1996, Timothy C. May wrote:
Suppose a tile is placed at some place on the grid, and another tile (possibly a different tile, possibly the same type of tile) is placed some distance away on the grid. The problem is this: Can a "domino snake" be found which reaches from the first tile to the second tile, with the constraint that edges must match up on all tiles? (And all tiles must be in normal grid locations, of course)
Intuitively (but very well not, I'm not informed enough to know) this might be a suitable problem for Hellman's DNA computer, the one used for chaining the shortest route including a defined number of cities?
No, massive parallelism does not help with the _general_ case. (For any specific instance, especially for a finite grid, obviously the amount of CPU power is directly relevant.) Even assuming Adleman's "DNA computer" works and scales relatively well, its CPU power only goes up roughly with the volume of the computer. While it may sound impressive to speak of "moles" of computers, or "swimming pools" of computers, such volumes are utterly inadequate to solve combinatorially-explosive problems. (Remember, it doesn't take a very big RSA product before the 10^75 elementary particles in the Universe are not enough to factor it in a billion times the age of the Universe even if every particle were a Cray! So much for a tank full of DNA computers.) The domino snake or tiling problem is a similarly explosive problem. Try playing around with some tiles on even a 5 x 5 grid, and then contemplate how large 25! is. Then think about a 10 x 10 grid, and 100! Then a 100 x 100 grid. And it may be that the domino snake reaching from tile A to tile B snakes around and about in a far, far larger grid space than this! (Even if one is confined to a 100 x 100 grid, easily displayed on a sheet of graph paper, no intelligence in the universe will ever be able to find a snake reaching from A to B, except in special situations (e.g., the same tile, etc.).) This sort of problem is the essence of some "zero knowledge interactive proof systems" (ZKIPS) sorts of proofs. I present such a snake as proof that I am who I say I am. (Because I just "made up" some random snake, then announced only the starting and stopping points, A and B. Nobody else in the universe could ever find such a snake, but I can display my solution as proof I generated it in the first place. Of course, once shown I have given the proof away to everyone. The ZKIPS trick is in twiddling the grid and/or tiles in such a way that I can give _probabalistic_ information away. I don't know how to do this for the domino snake problem, but it's easy to understand the Hamiltonian cycle version.) --Tim May (Late News: I just heard (12:30 p.m., PDT) that Seymour Cray is in extremely critical condition after suffering head injuries in a car crash. It will be a sad day if he dies, or is permanently disabled. Though he started working for the Agency in the 1950s, in a precursor to Control Data Corporation, and worked for them on various contracts in the next couple of decades, he was a true pioneer. (The CDC 6600, 7600, etc., and the Cray-1 were funded by contracts from the AEC and NSA, and the first few of each were delivered to Fort Meade, Los Alamos, Livermore, etc.)) We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."