子集和问题的O（1．414^n）链数DNA计算机算法  

An O（1.414^n） Volume Molecular Solutions for the Subset-Sum Problem on DNA-Based Supercomputing

作　　者：李肯立[1] 姚凤娟[1] 许进[2] 李仁发[1] 

机构地区：[1]湖南大学计算机与通信学院,长沙410082 [2]华中科技大学分子生物计算机研究所,武汉430074

出　　处：《计算机学报》2007年第11期1947-1953,共7页Chinese Journal of Computers

基　　金：国家自然科学基金(60603053;60503002;60533010);中国博士后科学基金(20060400845)资助.~~

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

关 键 词：DNA计算 子集和问题 分治法 并行处理 NP完全问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]