Improved Molecular Solutions for the Knapsack Problem on DNA-Based Supercomputing

The DNA-based supercomputation has solved hard computational problems such as NP-complete problems in polynomial increasing time by using its superparallel and high-density power. However, almost all the current DNA computing strategies are based on the enumerative method, which causes the size of the initial DNA strands to increase exponentially. How to decrease the number of DNA strands increasing exponentially in these applications is very important in the research on DNA computers. For the objectivity of solution of the knapsack problem which is a famous NP-complete problem with DNA computer, the strategy of divide-and-conquer is introduced into the DNA-based supercomputing and a DNA algorithm is proposed. The proposed algorithm consists of an n-bit parallel subtracter, an n-bit parallel searcher, and other four sub-procedures. It is demonstrated that the proposed algorithms can first reduce the number of DNA library strands from O(2\+q) to O(2\+\q/2\) to solve a q-dimension knapsack instance, while keeping the operation time not obviously changed. It is shown that the traditional technology can still bear importance even in designing DNA computer algorithm. Furthermore, this work indicates that the cryptosystems using public key are perhaps insecure, because, theoretically, the 120-variable knapsack public key can be easily broken provided that the technology of DNA computers is mature.