A Random Walk DNA Algorithm for the 3-SAT Problem

Title: A Random Walk DNA Algorithm for the 3-SAT Problem

Volume: 1 Issue: 1

Author(s): Wenbin Liu, Lin Gao, Qiang Zhang, Guandong Xu, Xiangou Zhu, Xiangrong Liu and Jin Xu

Affiliation:

Keywords: DNA Computing, the Satisfiability Problem, Random Walk Strategy, Plasmids DNA

Abstract: We present a randomized DNA algorithm for the 3-SAT problem based on the probabilistic algorithm proposed by Schöning. The basic idea of our algorithm is that the read of information is performed in linear DNA molecules, while the rewrite information is implemented in plasmid DNAs. Compared with previous works, our algorithm performs the flip of a variables value more easily and reliably, and the time complexity is also reduced to O(mn), where m is the number of clauses and n is the number of variables. Moreover, Schönings algorithm has been further improved recently for the case of 3-SAT by Hofmeister. We also demonstrate how to adapt this improvement in our new algorithm and the space complexity of our algorithm is then reduced to O[(4/3)n-3m (7/3)m], where m is the number of the maximal independent clauses. Up to now, this is the most volume-efficient algorithm for the 3-SAT based on DNA computing.

Cite this article as:

Liu Wenbin, Gao Lin, Zhang Qiang, Xu Guandong, Zhu Xiangou, Liu Xiangrong and Xu Jin, A Random Walk DNA Algorithm for the 3-SAT Problem, Current Nanoscience 2005; 1 (1) . https://dx.doi.org/10.2174/1573413052953129