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.