[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Directed Hamiltonian Path Problem
> 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.
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.
-- Thaddeus Beier email: [email protected]
Technology Development vox: 408) 286-3376
Hammerhead Productions fax: 408) 292-2244