Affordable Access

Publisher Website

Scalability of the surface-based DNA algorithm for 3-SAT

Authors
Journal
Biosystems
0303-2647
Publisher
Elsevier
Publication Date
Volume
85
Issue
2
Identifiers
DOI: 10.1016/j.biosystems.2005.12.002
Keywords
  • Dna Computing On Surfaces
  • Satisfiability
  • 3-Sat
Disciplines
  • Computer Science
  • Design

Abstract

Abstract Since Adleman first proposed DNA computing for the Hamiltonian path problem, several authors have reported DNA computing for 3-SAT. Previous research presented DNA computing on surfaces and demonstrated how to solve a four-variable four-clause instance of 3-SAT, and claimed that the surface-based approach was designed to scale up to larger problems. In this paper we establish an error model for the incomplete “mark” and imperfect “destroy” operations. By using the error model we argue that no matter how large the “mark” and “destroy” rates are we can always give satisfiable instances of 3-SAT such that no DNA strands remain on the surface at the end of the computation. By the surface-based approach the satisfiable instances of 3-SAT would be misdetermined to be unsatisfiable. Thus, the error leads to an incorrect result of the SAT computation. Furthermore, given the “mark” rate p and the “not-destroy” rate ρ , we find that the approach can only solve at most N-variable instances of 3-SAT problems, where N = [ ( 2 + β 2 + 2 1 + 2 β 2 ) / β 2 ] in which β = 1 − 1 / ( p + ρ q ) and q = 1 − p and [ a] is the greatest integer less than a or equal to a.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

FETI based algorithms for contact problems: scalab...

on Computer Methods in Applied Me... Jan 01, 2005

A surface-based DNA algorithm for the solving bina...

on Applied Mathematics and Comput... Jan 01, 2007
More articles like this..