SOLUTION OF THE KNAPSACK-PROBLEM BY DEOXYRIBONUCLEIC-ACID COMPUTING

Deoxyribonucleic acid (DNA) computing is executed to demonstrate that it is capable of solving a simple instance of the knapsack problem, wh ich is known to be NP-complete. DNA molecules with different lengths c oding the data are prepared, and the algorithm is implemented as molec ular biological processes such as ligation,polymerase chain reaction ( PCR), and DNA sequencing. The scheme of encoding, experimental procedu res and results are described, and the scalability of the present meth od is discussed. Reactions between DNA molecules are expected to reali ze a massively parallel computation of the order of 10(23) per mol.