Re: Directed Hamiltonian Path Problem

[thad@hammerhead.com (Thaddeus J. Beier)]

>  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 Beier                   email:  thad@hammerhead.com
   Technology Development             vox:  408) 286-3376
   Hammerhead Productions             fax:  408) 292-2244