A Caltech Library Service

Complexity of Restricted and Unrestricted Models of Molecular Computation

Winfree, Erik (1996) Complexity of Restricted and Unrestricted Models of Molecular Computation. In: DNA based computers. DIMACS series in discrete mathematics and theoretical computer science. No.27. American Mathematical Society , Providence, RI, pp. 187-198. ISBN 0821805185.

PDF - Submitted Version
See Usage Policy.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


In [9] and [2] a formal model for molecular computing was proposed, which makes focused use of affinity purification. The use of PCR was suggested to expand the range of feasible computations, resulting in a second model. In this note, we give a precise characterization of these two models in terms of recognized computational complexity classes, namely branching programs (BP) and nondeterministic branching programs (NBP) respectively. This allows us to give upper and lower bounds on the complexity of desired computations. Examples are given of computable and uncomputable problems, given limited time.

Item Type:Book Section
Winfree, Erik0000-0002-5899-7523
Additional Information:© 1996 American Mathematical Society. This work is supported in part by National Institute for Mental Health (NIMH) Training Grant # 5 T32 MH 19138-05; also by General Motors' Technology Research Partnerships program. The author would like to thank Paul W. K. Rothemund, Sam Roweis, and Matthew Cook for their stimulating discussion. Thanks especially to Jehoshua Bruck for pointing me to previous literature on branching programs. Thanks to my advisor John Hopfield for his support and encouragement.
Funding AgencyGrant Number
National Institute for Mental Health (NIMH) Training Grant 5 T32 MH 19138-05
General Motors Technology Research Partnerships ProgramUNSPECIFIED
Record Number:CaltechAUTHORS:20111024-134249923
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27383
Deposited By: Tony Diaz
Deposited On:26 Oct 2011 16:22
Last Modified:07 Mar 2015 00:26

Repository Staff Only: item control page