View source for Verification of 2HAM Systems

Given that the 2HAM allows for a greater variety of behaviors than the aTAM, and in fact in some sense for the transmission of information over arbitrary distances (by the placements of glues and general geometric shapes of arbitrarily large supertiles which are combining), it shouldn't be surprising that many verification problems are more difficult for the 2HAM than for the aTAM (see [[Verification of aTAM systems]]).

Several verification problems have been characterized in terms of their complexity, some of which include:


    1) Does 2HAM system $\mathcal[T]$ uniquely produce a given assembly?  This was shown to be co-NP-complete for 3D temperature 2 systems in the 2HAM in <ref name=Versus /> by Cannon, et al.  The complexity of this verification problem is still open in 2D.  (But note that it is solvable in polynomial time in the aTAM in both 2D and 3D.)
    2) Does 2HAM system $\mathcal{T}$ uniquely produce a given shape?  This was shown to be in co-NP for temperature 1 and co-NP-complete for temperature 2 by Cheng, et al. in <ref name=AGKS05g />
    3) Is a given assembly terminal in 2HAM system $\mathcal{T}$?  In <ref name=Versus /> this was shown to be uncomputable for temperature 2 systems in the 2HAM (while it is computable in polynomial time in the aTAM <ref name=ACGHKMR02 />,  and also for the 2HAM at temperature 1 <ref name=Versus />.)
    4) Given a 2HAM system $\mathcal{T}$, does it produce a finite terminal assembly?  This was shown to be uncomputable in <ref name=Versus />.
    5)Given a 2HAM system $\mathcal{T}$, does it produce an infinite terminal assembly?  This was shown to be uncomputable for temperature 2 2HAM systems in <ref name=Versus />.


==References==
<references>

<ref name =Versus><bibtex>
@techreport{Versus,
  author = "Sarah Cannon and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Matthew J. Patitz and Robert Schweller and Scott M. Summers and Andrew Winslow",
  title = "Two Hands Are Better Than One (up to constant factors)",
  number = "1201.1650",
  institution = "Computing Research Repository",
  year = 2012,
  url = "http://arxiv.org/abs/1201.1650"
}
</bibtex></ref>

<ref name =AGKS05g><bibtex>
@article{AGKS05g,
  author =	"Qi Cheng and Gagan Aggarwal and Michael H. Goldwasser and Ming-Yang Kao and Robert T. Schweller and Pablo Moisset de Espan\'{e}s",
  title =	"Complexities for Generalized Models of Self-Assembly",
  journal =	"SIAM Journal on Computing",
  volume = "34",
  pages = 	"1493--1515",
  year =	"2005",
}
</bibtex></ref>

<ref name =ACGHKMR02><bibtex>
@inproceedings{ACGHKMR02,
  author =   "Leonard M. Adleman and Qi Cheng and Ashish Goel and Ming-Deh A. Huang and David Kempe and Pablo Moisset de Espan\'{e}s and 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"
}

</references>

[[Category: 2HAM Results]]