Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2011 | public
Book Section - Chapter

The Power of Nondeterminism in Self-Assembly

Abstract

We investigate the role of nondeterminism in Winfree's abstract tile assembly model, which was conceived to model artificial molecular self-assembling systems constructed from DNA. By nondeterminism we do not mean a magical ability such as that possessed by a nondeterministic algorithm to search an exponential-size space in polynomial time. Rather, we study realistically implementable systems that retain a different sense of determinism in that they are guaranteed to produce a unique shape but are nondeterministic in that they do not guarantee which tile types will be placed where within the shape. We show a "molecular computability" result: there is an infinite shape S that is uniquely assembled by a tile system but not by any deterministic tile system. We show a "molecular complexity" result: there is a finite shape S that is uniquely assembled by a tile system with c tile types, but every deterministic tile system that uniquely assembles S has more than c tile types. In fact we extend the technique to derive a stronger (classical complexity theoretic) result, showing that the problem of finding the minimum number of tile types that uniquely assemble a given finite shape is Σ^(P)_(2)-complete. In contrast, the problem of finding the minimum number of deterministic tile types that uniquely assemble a shape is NP-complete [5].

Additional Information

© 2011 SIAM. Supported by NSERC Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing to Lila Kari, by the NSERC Undergraduate Student Research Awards (USRA) grant to Nathanial Bryans, and by the NSF Computing Innovation Fellowship grant to David Doty.

Additional details

Created:
August 19, 2023
Modified:
October 17, 2023