Solving the 3-SAT problem based on DNA computing.
The 3-SAT problem is an NP-complete problem, and many algorithms based on DNA computing have been proposed for solving it since Adleman's pioneering work. This paper presents a new algorithm based on the literal string strategy proposed by Sakamoto et al. Simulation results show that the maximal number of literal strings produced during the computing process is greatly reduced. Moreover, the length of the literal strings is also reduced from m to n at most.
Liu
Wenbin
W
Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan City 430074, China. wbliu@mail.hust.edu.cn
Gao
Lin
L
Liu
Xiangrong
X
Wang
Shudong
S
Xu
Jin
J
D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D004247:DNA / Q000737:chemistry*; D004277:DNA, Single-Stranded / Q000737:chemistry
D004277:DNA, Single-Stranded; D004247:DNA