CaltechAUTHORS
  A Caltech Library Service

Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model

Schiefer, Nicholas and Winfree, Erik (2016) Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.9818. Springer , Cham, Switzerland, pp. 165-182. ISBN 978-3-319-43993-8. https://resolver.caltech.edu/CaltechAUTHORS:20170718-122926337

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170718-122926337

Abstract

In isolation, chemical reaction networks and tile-based self-assembly are well-studied models of chemical computation. Previously, we introduced the chemical reaction network-controlled tile assembly model (CRN-TAM), in which a stochastic chemical reaction network can act as a non-local control and signalling system for tile-based assembly, and showed that the CRN-TAM can perform several tasks related to the simulation of Turing machines and construction of algorithmic shapes with lower space or program complexity than in either of its parent models. Here, we introduce a kinetic variant of the CRN-TAM and investigate the time complexity of computation and construction. We analyze the time complexity of decision problems in the CRN-TAM, and show that decidable languages can be decided as efficiently by CRN-TAM programs as by Turing machines. We also give a lower bound for the space-time complexity of CRN-TAM computation that rules out efficient parallel stack machines. We provide efficient parallel implementations of non-deterministic computations, showing among other things that CRN-TAM programs can decide languages in NTIME(f(n))∩coNTIME(f(n)) in O(f(n)+n+logc) time with 1−exp(−c) probability, using volume exponential in n. Lastly, we provide basic mechanisms for parallel computations that share information and illustrate the limits of parallel computation in the CRN-TAM.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/978-3-319-43994-5_11DOIArticle
ORCID:
AuthorORCID
Winfree, Erik0000-0002-5899-7523
Additional Information:© 2016 Springer International Publishing Switzerland. First Online: 14 August 2016. We acknowledge financial support from National Science Foundation grant CCF-1317694 and the Soli Deo Gloria Summer Undergraduate Research Fellowship at the California Institute of Technology. We also thank Dave Doty and Damien Woods for their insights.
Funders:
Funding AgencyGrant Number
NSFCCF-1317694
Caltech Summer Undergraduate Research Fellowship (SURF)UNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:9818
Record Number:CaltechAUTHORS:20170718-122926337
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170718-122926337
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:79158
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:18 Jul 2017 19:38
Last Modified:03 Oct 2019 18:16

Repository Staff Only: item control page