I. Solving NPComplete problems
A. Definitions:
1) A decision problem is in the class NP if there is no known algorithm
for it that will execute in polynomial time on a conventional computer,
and it can be solved in polynomial time using a nondeterministic computer
(Miller).
2) A problem is intractable if no polynomial time algorithm can possibly
be devised for it (Miller). In other words, as the complexity of intractable
problems increase, the time required to solve them increases at an exponential
rate (Adams).
3) A problem in NP is NPcomplete if every other problem in NP can be expressed
in terms of it by means of a polynomial time algorithm (Miller).
If any problem in NP is shown to be intractable then all NPcomplete
problems are intractable. However, if any NPcomplete problem can be solved
in polynomial time, all problems in NP become tractable (Miller).
B . How is it done?
A test tube of DNA strands can be used to simulate a nondeterministic
computer using the techniques of molecular biology. Theoretically speaking,
otherwise intractable problems can be implemented in polynomial time on
this DNA computer. One example is Adleman’s simulation of the Traveling
Salesman problem: known to be NPcomplete, the problem had an execution
time that was linear to the number of cities (Miller). However, Adleman’s
method of the exhaustive search algorithm is able to solve problems in
polynomial time only at the expense of exponential increases in volume
(Adams).
C. Implications to real life problems
Particularly in business planning and management science, many of the
cost optimization problems are NPcomplete and currently solved using
heuristic methods and other approximations. These problems include scheduling,
routing, and optimal use of raw materials, and correspond to problems
already solved, either theoretically or experimentally, using DNA computation
(Adams).
II. Cryptography
Currently, researchers have mapped a way in which DNA computers could
be used to crack messages encoded with Data Encryption Standard (DES)
(Bergquist). Although this problem has already been solved using conventional
techniques in a much shorter time than proposed by the DNA methods, the
DNA models are much more flexible, potent, and cost effective (Adams).
III. Turing Machine
A number of theoretical models for creating a universal DNA computer have
been developed, and mathematical proofs have shown that some models of
DNA computing are at least equivalent to a classical Turing machine (Adams).
In year 2001, Ehud Shapiro’s group at the Weizmann Institute in
Israel built a programmable and autonomous computing machine using the
DNA strands as inputs and the transition rules. Shapiro’s machine
was a “special case of the Turing Machine: a twostate, twosymbol
automaton” (Noble), but he is still hoping to develop a fully operational
molecular Turing Machine in the future (Parker).
IV. Patterning polysilicon directly without lithography
According to Adleman, by laying a grid of DNA precisely on top of silicon
substrates, very dense patterns of nanocrystals can seed polysilicon circuits
fabricated atop them. The accuracy of DNA enables circuits to be built
on a chip, molecule by molecule, instead of with bulk deposition and lithography.
Those substrates would pattern themselves onto flat sheets, which could
then be used to direct the placement of polysilicon materials atop them,
making up the actual circuit elements (Johnson).
