Authors: Bin Fu, Richard Beigel, and Frank Zhou
Abstract: We design volume-efficient molecular algorithms for all problems in #P, using only reasonable biological operations. In particular, we give a polynomial-time O(2n n2 log2n)-volume algorithm to compute the number of Hamiltonian paths in an n-node graph. This improves Adleman's celebrated n!-volume algorithm for finding a single Hamiltonian path.