广义分子计算模型在整数问题中的应用

Generalized Molecular Computational Model for NP Problems

  • 摘要: 分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.

     

    Abstract: DNA computing is a novel parallel computation paradigm. DNA, as the carrier of information and computing, is uncontrollable in biochemical reactions. There are many difficulties and limitations for the construction of a molecular universal computer. Based on the Turing machine and sticker model, a new generalized turing model (GTM) independent of biotechnology and only with an ordinary single tape Turing machine was proposed. Validation tests on the model showed that it can be used to solve the integer programming problem in the polynomial time and has obvious advantages in both computation accuracy and simply coding.

     

/

返回文章
返回
Baidu
map