Difference between revisions of "Building finite shapes in the aTAM"

From self-assembly wiki
Jump to navigation Jump to search
(References)
(References)
Line 11: Line 11:
 
<references>
 
<references>
  
<ref name =Winf98><bibtex>
+
<ref name =SolWin07><bibtex>
@phdthesis{Winf98,
+
@article{SolWin07,
   author = "Erik Winfree",
+
   author   = {David Soloveichik and
   title = "Algorithmic Self-Assembly of DNA",
+
              Erik Winfree},
   school = "California Institute of Technology",
+
   title     = {Complexity of Self-Assembled Shapes},
   year = "1998",
+
  journal  = {SIAM Journal on Computing},
   month = "June",
+
  volume    = {36},
 +
   number    = {6},
 +
   year     = {2007},
 +
  pages    = {1544-1569},
 +
  ee        = {http://dx.doi.org/10.1137/S0097539704446712},
 +
   bibsource = {DBLP, http://dblp.uni-trier.de}
 
}
 
}
 
</bibtex></ref>
 
</bibtex></ref>

Revision as of 12:45, 11 June 2013

Building finite shapes

In order to build any given finite shape, it is trivial to define a tile assembly system which will self-assemble it: simply create a unique tile type for every point in the shape so that the glue between each tile and each neighbor is unique to that pair in that location. Obviously, however, this is the worst possible construction in terms of tile type complexity. Soloveichik and Wifree, in [1], showed that as long as the shape can be scaled up (meaning that every point in the original shape is replaced by a square block of tiles of some fixed dimension) the tile type complexity for a finite shape \(S\) is bounded above and below by the Kolmogorov complexity of the shape. The Kolmogorov complexity of \(S\), denoted \(K(S)\), is the length in bits of the shortest program which, when run by a universal Turing machine, outputs exactly the points of \(S\) and then halts. They showed that the tile complexity of \(S\) is \(\Theta\left(\frac{K(S)}{\log K(S)}\right)\) by showing that the lower bound holds because otherwise it would contradict the Kolmogorov complexity of the shape, and for the upper bound they provided a construction in which a Turing machine is simulated inside of each scaled up block to read a compressed definition of \(S\) and determine which neighboring locations should have blocks filled in and then passing the program into those blocks and simulating the Turing machine within them, etc. Therefore, the scaling factor \(c\) is proportional to the running time of the Turing machine (and thus can be very large), and the tile complexity arises from the compressed definition of \(S\).

Another interesting aspect to the tile complexity of finite shapes was demonstrated by Bryans, Chiniforooshan, Doty, Kari, and Seki in [2] where they showed that there exist finite shapes which can self-assemble more tile type efficiently by nondeterministic systems than by deterministic, or directed, systems. Both types of systems always create the exact same shape, but where a directed system does so by ensuring that no matter which assembly sequence is followed, a given location always receives a tile of the same type, a nondeterministic system may allow tiles of differing types to occupy a particular position based on the assembly sequence followed. They also showed that the problem of determining the minimum number of tile types which are required to uniquely assemble a given finite shape, if the system isn't constrained to being directed, is complete for the complexity class \(\Sigma^P_2 = NP^{NP}\), while it was shown by Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanés, and Rothemund in [3] to be NP-complete for directed systems. These results suggest that such nondeterminism adds power and complexity to the aTAM.


References

  1. David Soloveichik, Erik Winfree - Complexity of Self-Assembled Shapes
    SIAM Journal on Computing 36(6):1544-1569,2007
    Bibtex
    Author : David Soloveichik, Erik Winfree
    Title : Complexity of Self-Assembled Shapes
    In : SIAM Journal on Computing -
    Address :
    Date : 2007
  2. Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari,, Shinnosuke Seki - The power of nondeterminism in self-assembly
    SODA '11: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms pp. 590--602,2011
    Bibtex
    Author : Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari,, Shinnosuke Seki
    Title : The power of nondeterminism in self-assembly
    In : SODA '11: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms -
    Address :
    Date : 2011
  3. eonard M. Adleman, Qi~Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo~Moisset de Espanés,, Paul W. K. Rothemund, title = {Combinatorial optimization problems in self-assembly}, booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing}, year = {2002}, pages = {23--32}, -
    Bibtex
    Author : eonard M. Adleman, Qi~Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo~Moisset de Espanés,, Paul W. K. Rothemund,
    title = {Combinatorial optimization problems in self-assembly},
    booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},
    year = {2002},
    
    pages = {23--32},
    Title :
    In : -
    Address :
    Date :