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

A Random Walk DNA Algorithm for the 3-SAT Problem

Buy Article:

$68.00 + tax (Refund Policy)

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

Keywords: DNA Computing; Plasmids DNA; Random Walk Strategy; the Satisfiability Problem

Document Type: Review Article

Affiliations: School of Computer Science and Engineering, Wenzhou Normal College, Wenzhou City 325027, China.

Publication date: January 1, 2005

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