A PARALLEL ALGORITHM FOR SOLVING SAT PROBLEM BASED ON DNA COMPUTING

M. Darehmiraki

Keywords

NP-complete, DNA computing, SAT problem

Abstract

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).

Important Links:

Go Back