4. Aldeman’s Hamilton path problem:-

4. Aldeman’s Hamilton path problem:-


The Hamiltonian Path problem.

In 1994, Leonard M. Adleman solved an unremarkable computational problem with a remarkable technique. It was a problem that a person could solve it in a few moments or an average desktop machine could solve in the blink of an eye. It took Adleman, however, seven days to find a solution. Why then was this work exceptional? Because he solved the problem with DNA. It was a landmark demonstration of computing on the molecular level.

The type of problem that Adleman solved is a famous one. It's formally known as a directed Hamiltonian Path (HP) problem, but is more popularly recognized as a variant of the so-called "traveling salesman problem." In Adleman's version of the traveling salesman problem, or "TSP" for short, a hypothetical salesman tries to find a route through a set of cities so that he visits each city only once. As the number of cities increases, the problem becomes more difficult until its solution is beyond analytical analysis altogether, at which point it requires brute force search methods. TSPs with a large number of cities quickly become computationally expensive, making them impractical to solve on even the latest super-computer. Adleman’s demonstration only involves seven cities, making it in some sense a trivial problem that can easily be solved by inspection. Nevertheless, his work is significant for a number of reasons.

It illustrates the possibilities of using DNA to solve a class of problems that is difficult or impossible to solve using traditional computing methods.

It's an example of computation at a molecular level, potentially a size limit that may never be reached by the semiconductor industry. It demonstrates unique aspects of DNA as a data structure. It demonstrates that computing with DNA can work in a massively parallel fashion.