DNA computing, also known as molecular computing, is a new approach to massively parallel computation based on groundbreaking 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 and Adleman 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 has estimated that to factor a 1000-bit number following Adleman's original approach, the required amount of solution would be 10200000 liters. However, Adleman has observed that a DNA computer sufficient to search for 256 DES keys would occupy only a small set of test tubes. In any case, DNA computing is just classical computing, albeit highly parallelized; thus with a large enough key, one should be able to thwart any DNA computer that can be built. With quantum computing , on the other hand, factoring can theoretically be done in (quantum) polynomial time, so quantum computing might be viewed with more concern than DNA computing.
|
