摘要：如何减少DNA计算机在求解大型科学问题中以问题输入纯指数增长的DNA链数，已成为DNA计算机研究的重要内容。本文将分治策略应用于子集积问题的DNA分子计算中，提出一种求解子集积问题的新的DNA计算机算法。该算法由n位数据搜索器和其它五个子算法组成，其DNA链数可达到亚指数的O（2^q/2），其中q为子集积问题的维数。与最近文献结论进行的对比分析表明：新算法将求解子集积问题所需的DNA链数从O（2^q）减少至O（2^q/2），最大链长度减少为原来的1／2。因此，利用新算法在试管级水平上能将可破解的子集积公钥的维数从60提高到120。

关键词：dna计算 np完全问题 子集积问题 分治法 

单位：湖南大学计算机与通信学院; 湖南长沙410082; 湖南公安高等专科学校计算机系; 湖南长沙410136