DNA Computing Solves the 3-SAT Problem with a Small Solution Space

Xiaolong      Wang; Zhenmin      Bao; Jingjie      Hu; Deming      Gou

Abstract

A simple 4-variable-8-clause 3 – SAT problem is solved using a DNA computing algorithm and experimental protocols amenable to automation. The proposed DNA computing algorithm can solve an n-variable m-clause SAT problem in m+1 steps including 9m operations, and the amount of time required increases proportional to m. Our algorithm does not first generate a large pool of all possible solutions, but rather starts from an empty test tube and then generates solutions that partially satisfy the SAT formula. These partial solutions are then extended step by step by the addition of new variables and incorrect ones are eliminated as soon as they fail to satisfy the conditions. This algorithm eliminates the need to generate the full-solution DNA library, which drastically reduces the number of DNA molecules that must be present throughout the computing process. Through computer experiment, it is observed that the maximum number of DNA strands required is 20.48n when n = 50, and the exponent ratio decreases logarithmically with the increasing of the number of variables n. When n is set to be 100 and 200, the predicted amount of DNA strands required are respectively within several nanomole and micromole. Hence, compared with the conventional brute-force search, our algorithm is more space efficient and can be scaled-up to solve large SAT problems.

Keywords: DNA computing, SAT problem, space complexity, time complexity

« Previous Next »