Generalized Molecular Computational Model for NP Problems

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.