A Parallel Algorithm for Solving SAT Problem based on DNA Computing

摘要

In this paper, stickers are used to construct a solution space of DNA for the satisfiability (SAT) problem. Simultaneously DNA operations are applied in the sticker-based model to develop a DNA algorithm. The result of the proposed algorithm shows that the SAT problem is resolved with biological operation in the sticker-based model for solution space of sticker. Furthermore, this work presents clear evidence of the ability of DNA computing to solve NP-complete problem. The potential of DNA computing for the SAT problem is promising, given the operational time complexity of O(n).