Difference between revisions of "Verification of aTAM systems"

From self-assembly wiki
Jump to navigation Jump to search
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
Several "verification problems" (answering the question of whether or not a given system has a specific property) have been studied in relation to the aTAM, and characterized by their complexity.  Among them are:
 
Several "verification problems" (answering the question of whether or not a given system has a specific property) have been studied in relation to the aTAM, and characterized by their complexity.  Among them are:
  
−
    1) Does aTAM system $\mathcal{T}$ uniquely produce a given assembly?  This was shown to require time polynomial in the size of the assembly and tile set by Adleman, et al. in <ref name=ACGHKMR02 />.
+
1) Does aTAM system $\mathcal{T}$ uniquely produce a given assembly?  This was shown to require time polynomial in the size of the assembly and tile set by Adleman, et al. in <ref name=ACGHKMR02 />.
−
    2) Does aTAM system $\calT$ uniquely produce a given shape?  This was shown to be in co-NP-complete for temperature 1 by Cannon, et al. in \cite{Versus} and co-NP-complete for temperature 2 in <ref name=AGKS05g /> by Cheng, et al.
+
 
−
    3) Is a given assembly terminal in aTAM system $\mathcal{T}$?  This was shown to require time linear in the size of the assembly and tile set in <ref name=ACGHKMR02>
+
2) Does aTAM system $\calT$ uniquely produce a given shape?  This was shown to be in co-NP-complete for temperature 1 by Cannon, et al. in <ref name=Versus /> and co-NP-complete for temperature 2 in <ref name=AGKS05g /> by Cheng, et al.
−
    4) Given an aTAM system $\calT$, does it produce a finite terminal assembly?  An infinite terminal assembly?  These were both shown to be uncomputable in <ref name=Versus />.
+
 
−
\end{enumerate}
+
3) Is a given assembly terminal in aTAM system $\mathcal{T}$?  This was shown to require time linear in the size of the assembly and tile set in <ref name=ACGHKMR02 />
 +
 
 +
4) Given an aTAM system $\calT$, does it produce a finite terminal assembly?  An infinite terminal assembly?  These were both shown to be uncomputable in <ref name=Versus />.
 +
 
  
 
==References==
 
==References==
Line 31: Line 34:
 
</bibtex></ref>
 
</bibtex></ref>
  
−
<ref name =AdChGoHu01><bibtex>
 
−
@article{AdChGoHu01,
 
−
  author =      "Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang",
 
−
  year =        "2001",
 
−
  title =      "Running time and program size for self-assembled squares",
 
−
  booktitle = "Proceedings of the 33rd Annual ACM Symposium on Theory of Computing",
 
−
  publisher = "ACM"
 
−
  pages    = {740--748}
 
−
}
 
−
</bibtex></ref>
 
−
 
−
<ref name =AGKS05g><bibtex>
 
−
@article{AGKS05g,
 
−
  author =      "Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, and Pablo Moisset de Espan&eacute;s",
 
−
  year =        "2005",
 
−
  title =      "Complexities for generalized models of self-assembly",
 
−
  journal = "SIAM Journal on Computing",
 
−
  volume = "34",
 
−
  pages    = {1493--1515}
 
−
}
 
−
</bibtex></ref>
 
  
 
<ref name =Versus><bibtex>
 
<ref name =Versus><bibtex>
Line 67: Line 49:
  
 
[[Category:Results in the aTAM]]
 
[[Category:Results in the aTAM]]
 +
[[Category:Self-assembly]]

Latest revision as of 15:17, 27 May 2014

Several "verification problems" (answering the question of whether or not a given system has a specific property) have been studied in relation to the aTAM, and characterized by their complexity. Among them are:

1) Does aTAM system \(\mathcal{T}\) uniquely produce a given assembly? This was shown to require time polynomial in the size of the assembly and tile set by Adleman, et al. in [1].

2) Does aTAM system \(\calT\) uniquely produce a given shape? This was shown to be in co-NP-complete for temperature 1 by Cannon, et al. in [2] and co-NP-complete for temperature 2 in [3] by Cheng, et al.

3) Is a given assembly terminal in aTAM system \(\mathcal{T}\)? This was shown to require time linear in the size of the assembly and tile set in [1]

4) Given an aTAM system \(\calT\), does it produce a finite terminal assembly? An infinite terminal assembly? These were both shown to be uncomputable in [2].


References

  1. ↑ 1.0 1.1 Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espan\'es, Paul W. K. Rothemund - Combinatorial optimization problems in self-assembly
    Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing pp. 23--32,2002
    Bibtex
    Author : Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espan\'es, Paul W. K. Rothemund
    Title : Combinatorial optimization problems in self-assembly
    In : Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing -
    Address :
    Date : 2002
  2. ↑ 2.0 2.1 Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow - Two Hands Are Better Than One (up to constant factors)
    Technical Report, Computing Research Repository (1201.1650),2012
    http://arxiv.org/abs/1201.1650
    Bibtex
    Author : Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow
    Title : Two Hands Are Better Than One (up to constant factors)
    In : Technical Report, Computing Research Repository -
    Address :
    Date : 2012
  3. ↑ Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Pablo Moisset de Espan\'es - Complexities for Generalized Models of Self-Assembly
    SIAM Journal on Computing 34:1493--1515,2005
    Bibtex
    Author : Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Pablo Moisset de Espan\'es
    Title : Complexities for Generalized Models of Self-Assembly
    In : SIAM Journal on Computing -
    Address :
    Date : 2005
Retrieved from "http://self-assembly.net/wiki/index.php?title=Verification_of_aTAM_systems&oldid=1193"