Application of Generalized Molecular Computation Model in Set Covering Problem

Because the existing computing models are mostly based on biological technology and lack versatility and accuracy, a new generalized molecular computation model (GCCM), which consisting a general Turing machine, writing tape, working tape and network, and a special topology mapping between the writing and the working tapes, was proposed. The model combines DNA computing and traditional computer model. Because of its big storage and high parallelism inherited from DNA computing, the model can solve NP complete problems by transforming space complexity to time complexity. In this paper, the definition and working principle of model were first introduced; then based on the model, a new algorithm of the set covering problem was put forth and its working process was shown. Finally, an instance was given to verify the ability of the algorithm to solve the set covering problem in polynomial time.