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 http://resolver.caltech.edu/CaltechAUTHORS:20111024-134249923
- Submitted Version
See Usage Policy.
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111024-134249923
In  and  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|
|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.|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||26 Oct 2011 16:22|
|Last Modified:||07 Mar 2015 00:26|
Repository Staff Only: item control page