DNA;Lipton">
### Question 111. 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^{200000} liters, which
is not practical. However, Adleman has observed that a DNA computer sufficient
to search for 2^{56} 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.