DNA Computing Solves the 3-SAT Problem with a Small Solution Space
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.
No Supplementary Data
No Article Media
Document Type: Research Article
Publication date: November 1, 2008
More about this publication?
- Current Nanoscience publishes authoritative reviews and original research reports, written by experts in the field on all the most recent advances in nanoscience and nanotechnology. All aspects of the field are represented including nano- structures, synthesis, properties, assembly and devices. Applications of nanoscience in biotechnology, medicine, pharmaceuticals, physics, material science and electronics are also covered. The journal is essential to all involved in nanoscience and its applied areas.
- Editorial Board
- Information for Authors
- Subscribe to this Title
- Ingenta Connect is not responsible for the content or availability of external websites