Breadth First Search 3SAT Algorithms for DNA Computers

This paper demonstrates that some practical 3SAT algorithms on conventional computers can be implemented on a DNA computer as a polynomial time breadth first search procedure based only on the fundamental chemical operations identified by Adleman and Lipton's method. In particular, the Monien-Speckenmeyer algorithm, when implemented on DNA, becomes an $O(n\cdot\max\{m^2,n\})$ time, $2^{0.6942 n}$ space algorithm, with significant increase in time and significant decrease in space. This paper also proposes a fast breadth first search method with fixed split points. The running time is at most twice as that of Lipton. Although theoretical analysis of the algorithm is yet to be done, simulations on a conventional computer suggest that the algorithm could significantly reduce the search space for 3SAT for most cases. If the observation is correct, the algorithm would allow DNA computers to handle 3SAT formulas of more than 120 variables, thereby doubling the limit given by Lipton