paper

Molecular Computation of Solutions To Combinatorial Problems

  • Authors:
Read the paper

đź“ś Abstract

The potential of molecular computation to solve combinatorial problems that are impractical for traditional electronic computers is demonstrated by executing a molecular algorithm to solve an instance of the directed Hamiltonian path problem. Given graph G matching the complexity of a 7-city traveling salesman problem, the problem of determining the shortest path among these 7 cities, starting at a particular city, visiting each city only once, is solved. The instance of the HPP solved here is a NP-complete problem solving for a path from 'A' to 'G'. This result suggests the potential of molecular computation as the basis for new computations on a much larger scale.

✨ Summary

Leonard M. Adleman’s 1994 paper titled “Molecular Computation of Solutions To Combinatorial Problems” presents a groundbreaking experiment demonstrating the potential of DNA as a medium for solving complex combinatorial problems. The paper showcases an experiment solving an instance of the Hamiltonian path problem (HPP), a known NP-complete problem, using molecular computation. This DNA computing approach represents a novel form of computing that can potentially solve certain types of problems more efficiently than conventional silicon-based computers.

The paper and its findings have had a significant impact on the field of computation, particularly in developing the concept and field of DNA computing. Subsequent research has built on Adleman’s work in exploring the capabilities and limitations of molecular computation.

Several studies citing this work include:

  1. Lipton, Richard J. “DNA Solution of Hard Computational Problems.” Science, Vol. 268, Issue 5210, pp. 542-545, 1995.
    • This paper explores further DNA-based algorithms for solving computationally intensive problems, fundamentally acknowledging Adleman’s pioneering work.

  2. Feynman, R. P., “There’s Plenty of Room at the Bottom,”. Lecture which explores the potential for future computing methods, where Adleman’s work is often referenced within the context of nanotechnology as computation.

  3. Beckmann, J. S., “DNA Computing: Is It Really That Powerful?” Nature Biotechnology 14, 760–763 (1996).
    • A critique and exploration of the limits and scalability of DNA computation, citing Adleman’s original experiment as a key component of the DNA computing narrative.

The innovative nature of the experiment led to a new field of research and spurred further exploration into biomolecular computation methods. Despite initial optimism, ongoing research continues to address challenges such as scalability and error rates in practical applications of DNA computing.