Research Repository

A Random Walk DNA Algorithm for the 3-SAT Problem

Liu, Wenbin, Gao, Lin, Zhang, Qiang, Xu, Guandong, Zhu, Xiangou, Liu, Xiangrong and Xu, Jin (2005) A Random Walk DNA Algorithm for the 3-SAT Problem. Current Nanoscience, 1 (1). pp. 85-90. ISSN 1573-4137

Full text for this resource is not available from the Research Repository.


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 variable’s 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öning’s 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.

Item Type: Article
Uncontrolled Keywords: ResPubID22919. DNA computing, DNA algorithm, Satisfiability problem, 3-SAT problem, Random Walk Strategy, plasmids DNA, Schöning, genetics
Subjects: FOR Classification > 0102 Applied Mathematics
FOR Classification > 0103 Numerical and Computational Mathematics
Faculty/School/Research Centre/Department > School of Engineering and Science
Related URLs:
Depositing User: VUIR
Date Deposited: 02 Feb 2012 05:16
Last Modified: 02 Feb 2012 05:16
ePrint Statistics: View download statistics for this item

Repository staff only

View Item View Item

Search Google Scholar