# Verification of aTAM systems

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 -
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 -
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 -