Computer Science – Computational Complexity
Scientific paper
2010-06-15
Computer Science
Computational Complexity
Accepted to SODA 2011. The previous version of this paper (which appears in the SODA proceedings) had open questions about com
Scientific paper
We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), which was conceived to model artificial molecular self-assembling systems constructed from DNA. Of particular practical importance is to find tile systems that minimize resources such as the number of distinct tile types, each of which corresponds to a set of DNA strands that must be custom-synthesized in actual molecular implementations of the aTAM. We seek to identify to what extent the use of nondeterminism in tile systems affects the resources required by such molecular shape-building algorithms. We first show a "molecular computability theoretic" result: there is an infinite shape S that is uniquely assembled by a tile system but not by any deterministic tile system. We then show an analogous phenomenon in the finitary "molecular complexity theoretic" case: 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 Sigma-P-2-complete. In contrast, the problem of finding the minimum number of deterministic tile types that uniquely assemble a shape was shown to be NP-complete by Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espan\'es, and Rothemund (Combinatorial Optimization Problems in Self-Assembly, STOC 2002). The conclusion is that nondeterminism confers extra power to assemble a shape from a small tile system, but unless the polynomial hierarchy collapses, it is computationally more difficult to exploit this power by finding the size of the smallest tile system, compared to finding the size of the smallest deterministic tile system.
Bryans Nathaniel
Chiniforooshan Ehsan
Doty David
Kari Lila
Seki Shinnosuke
No associations
LandOfFree
The Power of Nondeterminism in Self-Assembly does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Power of Nondeterminism in Self-Assembly, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Power of Nondeterminism in Self-Assembly will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-104369