Directed Hamiltonian Path Problem

Perry E. Metzger perry at piermont.com
Tue Nov 28 03:39:39 PST 1995



Timothy C. May writes:
> The work by Adleman on "vats of computers" is intriguing, but is no real
> solution to the problem of exponential or superexponential growth: a
> problem that Adleman's vat could solve with a fish tank full of DNA
> computers in a day could be easily outpaced by a key length "only" a bit
> longer.

Indeed. Its the problem with innumeracy. People don't understand that
if, say, a problem is O(2^N), and a problem of size 1000 requires a
liter of fluid, a problem of size 2000 requires 
107150860718626732094842504906000181056140481170553360744375038837035\
105112493612249319837881569585812759467291755314682518714528569231404\
359845775746985748039345677748242309854210746050623711418779541821530\
464749835819412673987675591655439460770629145711964776865421676604298\
31652624386837205668069376 liters of fluid.

I'll note that is something like
107150860718626732094842504906000181056140481170553360744375038837035\
105112493612249319837881569585812759467291755314682518714528569231404\
3598457757469857480393456777482423098542107460506237114187795418
times more liters of fluid than there are fundamental particles in the
universe -- being too lazy to calculate the number of fundamental
particles in a liter, I won't make the more relevant statement of what
multiple of the number of particles in the universe the number of
particles in that number of liters of fluid would be.

The stuff on quantum factoring worries me more than Adleman fluid -- I
never can get an explanation of it clear enough to decide if it is
more than a theoretical concern.

Perry






More information about the cypherpunks-legacy mailing list