Complexity and Error Analysis of Four DNA Algorithms
for the Directed Hamiltonian Path Problem
Complexity and Error Analysis of Four DNA Algorithms
for the Directed Hamiltonian Path Problem Abstract: We analyze four published experiments on solving the Directed Hamiltonian Path Problem. It turns out that the algorithms involved are either (1) Exhaustive Search or (2) Dynamic Programming. It is clear that neither approach is generally applicable to problems of interesting size. On one hand, Exhaustive Search either takes impossibly much time (on conventional computers) or impossibly much material (on DNA computers). On the other hand Dynamic Programming, first used for this problem by Held and Karp in 1962, is known to require impossibly much storage of intermediate results.
Last modified: March 15, 1998