一种广义分子计算模型及其在 NP问题中的应用

• 作者: 余文 宁建国 李艳梅
• 来源期刊: 计算机应用研究
• 关键词: 广义分子计算模型 图灵机 SAT问题
• 年，卷（期）: 2014,（11）
• 页码范围: 3353-3356
• 页数: 4页
• 分类号: TP301
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2014.11.035

摘要

目前各种分子计算模型多基于生物技术，求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题，尚不似传统计算机般通用。为此，提出一种基于图灵机的广义分子计算模型，其由一台单带图灵机、一条单向只写带和一条工作带组成，通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题（SAT），比现有分子计算模型在计算准确性和通用性上存在明显优势。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁建国	北京理工大学机电学院爆炸科学与技术国家重点实验室	175	1919	23.0	36.0
2	余文	北京邮电大学计算机学院智能通信软件多媒体北京市重点实验室	5	27	3.0	5.0
3	李艳梅	北京理工大学机电学院爆炸科学与技术国家重点实验室	2	6	2.0	2.0