In 1959, Richard Feynman gave a visionary talk describing the possibility of building computers that were "sub-microscopic." Last fall, in a revolutionary paper whose consequences may prove to be among the major scientific breakthroughs of this century, Leonard Adleman showed how computations could be carried out using simple DNA manipulations.
In particular, Leonard Adleman, of the Department of Computer Science and Institute for Molecular Medicine and Technology at the University of Southern California, found a solution to an instance of the directed Hamiltonian path problem, an "NP-complete", or "hard" problem.
I will give an overview of how computational problems are ranked by difficulty, leading to the important class of "NP-complete" problem, and why the massive parallelism of solution-phase chemistry was crucial to Adleman's work. I will then give a ("nondeterministic") algorithm for solving the directed Hamiltonian path problem and outline how the inputs were encoded and the algorithm carried out by Adleman at the molecular level, where a complete solution was encoded in a single molecule.
Finally, I will cite some breath-taking comparisons between these kinds of molecular-level computations and present computer technology, focusing in particular on number of computations per second, energy efficiency, and information representation density, whereupon we can jointly ruminate on the "eventual emergence of a general purpose computer consisting of nothing more than a single macromolecule conjugated to a ribosomelike collection of enzymes that act on it."