Re: provably hard PK cryptosystems

[Asgaard <asgaard@Cor.sos.sll.se>]

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?

Asgaard