Re: Directed Hamiltonian Path Problem
At 4:04 AM 11/28/95, Thaddeus J. Beier wrote:
I am curious on whether there are any applications of the directed Hamiltonian path problem to cryptography, zero-knowledge proofs, etcetera. My reaosn for asking is that I've come across something in my field (molecular genetics) that can be used to solve such problems in a couple of weeks or so. -Allen
Secret sharing can be done by Hamiltonian paths. No public key code has been found to take advantage of those, or any other NP complete problem, so far as I know. DNA computing really doesn't solve the Hamiltonian graph problem, it just makes the biggest one that you can solve a little bit bigger. 500 point graphs remain insoluble (pun unitended) for earth-sized vats of DNA.
Really.
Thaddeus beat me to the punch, as I was going to say just about the same thing. 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. Check the archives for many articles on this topic. Also, check the Web search engines for conferences, papers, etc. on this. --Tim May Views here are not the views of my Internet Service Provider or Government. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^756839 | black markets, collapse of governments. "National borders are just speed bumps on the information superhighway."
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
participants (2)
-
Perry E. Metzger -
tcmay＠got.net