Starting with 10^23 DNA snippets in 1/50 of a teaspoon we estimated in class that a big bathtub would contain 10^31 such pieces. That's a very small number compared to the number of paths of length 100 in a graph where each node is connected to 10 other nodes. That number is 10^100. (Keep in mind that the DNA pieces are not going to avoid repetition of nodes in these paths. They are just a bunch of dumb chemicals, they are not travel agents.)
So even if we assume that no activity is wasted on shorter paths, and none on longer paths, and that each possible path does get formed, and that no paths gets formed more than once (a very generous assumption), and that we can fish out the right answer(s) or else be able to make sure there is no path by making sure that not even one molecule of certain properties got formed, even with all these generous assumptions this approach will not solve Hamiltonian Path problems approaching 100 nodes in size. And that's not a large problem.
What is the merit then? It gave us a chance to hone our understanding of asymptotics and constant factors. It also may provide a way to increase the size of Hamiltonian Path problems (and other NP-complete problems) that we can handle. And most importantly, it may open up yet other ways to compute, Hamiltonian Path or whatever else.
Last edited (or copied to this place) at 9:22 AM, Wednesday, October 11, 1995.