子集和问题的O(1.414n)链数DNA计算机算法

随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.

An O(1.414n) 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.