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

How to decrease the volume in DNA computers has become an important problem in the research of DNA computing. And the poor scalability in the DNA-based algorithms roots in the poor scalability of the DNA models. In this paper, we modified Chang´s model by add biological operations the operations of fluorescence labeling and gel electrophoresis into Adleman-Lipton model and change the structure of the DNA strands by translating the final binary result into real length. Based on it, a new DNA algorithm for subset-product problem is also proposed where the strategy of divide and conquer is introduced. The proposed algorithm can solve the w-dimension subset-product problem by using the O(1.414ⁿ) 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(2ⁿ) DNA strands is used. Therefore, the scale of the public key cryptosystem can be theoretically broken using biological operations may be enlarged from 60 to 120 variables.