What is DNA Computing?

DNA computing, also known as molecular computing, is a new approach to massively parallel computation based on ground-breaking work by Adleman. He used DNA to solve a seven-node Hamiltonian path problem, a special case of an NP-complete problem that attempts to visit every node in a graph exactly once. (This special case is trivial to solve with a conventional computer, or even by hand, but illustrates the potential of DNA computing.)

A DNA computer is basically a collection of specially selected DNA strands whose combinations will result in the solution to some problem. Technology is currently available both to select the initial strands and to filter the final solution. The promise of DNA computing is massive parallelism: with a given setup and enough DNA, one can potentially solve huge problems by parallel search. This can be much faster than a conventional computer, for which massive parallelism would require large amounts of hardware, not simply more DNA.

Research on DNA computing is ongoing; Lipton [Lip94] and Adleman [Adl95] have extended on Adleman's original work with more efficient designs of possible DNA computers.

The impact of DNA computing on cryptography remains to be determined. Beaver [Bea95] has shown that to factor a 1000-bit number following Adleman's original approach of solving an NP-complete problem, the required amount of solution would be 10²⁰⁰⁰⁰⁰ liters, which is not practical. However, Adleman has observed that a DNA computer sufficient to search for 2⁵⁶ DES keys would occupy only a small set of test tubes [Adl96]. In any case, DNA computing is just classical computing, albeit highly parallelized, so with a large enough key, one should be able to thwart any DNA computer that can be built. With quantum computing (see Question 109), on the other hand, factoring can theoretically be done in (quantum) polynomial time, so quantum computing seems to be much more of a concern than DNA computing.

| Question 112 |