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

摘要：

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

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

所属期刊栏目：30

分类号：TP301(计算技术、计算机技术)

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

在线出版日期：2008-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1947-1953