An O(1.414~n) Volume Molecular Solutions for the Subset-Sum Problem on DNA-Based Supercomputing

How to decrease the volumes in DNA computers has become an important research area in DNA computing.It is showed that the poor scalability in the DNA-based algorithms roots in the poor scalability of the DNA models.In this paper,a DNA model for good scalability is proposed.It is based on biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model.The method of fluorescence labeling and the technique of gel electrophoresis are incorporated into the model.Based on it,a new DNA algorithm for solution of the subset-sum problem is proposed where the strategy of divide and conquer and a new designed algorithm of ParallelSearcher are introduced.The proposed algorithm can solve the n-dimension subset-sum instances by using the O(1.414n) shorter DNA strands on the condition of not varying the time complexity,as compared by far the best molecular algorithm for it in which O(2n) DNA strands is used.Therefore,the scale of the public key cryptosystem that can be theoretically broken using the present biological technology may be enlarged from 60 to 120 variables.