Skip to main content
padlock icon - secure page this page is secure

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

Buy Article:

$68.00 + tax (Refund Policy)

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 References
No Citations
No Supplementary Data
No Article Media
No Metrics

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

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
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more