Information Technology Reference
In-Depth Information
Shortly after the appearance of Adleman's work, the American mathematician
Richard Lipton from Princeton demonstrated how DNA can be used to encode
binary numbers and to solve the problem of satisfying a logical expression. Its
essence is that, given some logical expression involving
n
logical variables, one
needs to find all combinations of variable values that make the expression true.
Traditional techniques reduce this problem to the sorting of 2
n
combinations.
Lipton showed that all these combinations can be easily encoded by DNA, and
then the Adleman method can be applied. Lipton also proposed a way of breaking
DES (the data encryption standard), treated as a kind of a logical expression.
In addition several other applications of DNA computing were proposed. At the
University of Wisconsin, the problem of delivering four types of pizza to four
destinations, which implied 16 different answers, was solved with the help of DNA.
Scientists from the Princeton University solved the combinatorial chess problem:
with the help of RNA they found the correct move of a chess knight on the board of
nine squares (a total of 512 variants).
In general, the future of DNA computing remains uncertain. The fact that for
more than 10 years after the appearance of Adleman's work no workable computing
device has been created based on his suggestions apparently indicates serious
difficulties of practical implementation of this approach. At the same time the
originality of this approach is attracting new researchers and ensures its support
by DARPA (Defense Advanced Research Projects Agency).
